글 읽기 - [c++] bfs로 풀었는데 반레가 뭐가있을까요?

gi5005 3년 전 0

어디서 틀리는지 모르겠습니다

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 500
int mp[MAX][MAX];
bool vst[MAX][MAX];
struct pos
{
	int x;
	int y;
	int f;
};
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	while (T--)
	{
		bool insung = false;
		int H, W, O, F, sx, sy, ex, ey;
		cin >> H >> W >> O >> F >> sx >> sy >> ex >> ey;
		memset(mp, 0, sizeof(mp));
		memset(vst, false, sizeof(vst));
		for (int i = 0; i < O; i++)
		{
			int x, y, l;
			cin >> x >> y >> l;
			mp[y][x] = l;
		}
		queue<pos> q;
		q.push({sx, sy, F});
		vst[sy][sx] =true;
		while (!q.empty())
		{
			pos cur = q.front();
			q.pop();
			int curP = mp[cur.y][cur.x];
			if (cur.x == ex && cur.y == ey)
			{
				cout << "잘했어!!\n";
				insung = true;
				break;
			}
			if (cur.f <= 0)
				continue;
			for (int i = 0; i < 4; i++)
			{
				pos nx;
				nx.x = cur.x + dx[i];
				nx.y = cur.y + dy[i];
				nx.f = cur.f - 1;
				int nxP = mp[nx.y][nx.x];
				int diff = nxP - curP;
				if (nx.x <= 0 || nx.x > W || nx.y <= 0 || nx.y > H)
					continue;
				if (diff > 0 && nx.f < diff)
					continue;
				if (vst[nx.y][nx.x])
					continue;
				if (nx.f < 0)
					continue;
				vst[nx.y][nx.x] = true;
				q.push(nx);
			}
		}
		if(insung) continue;
		cout << "인성 문제있어??\n";
	}
}

newdeal 3년 전 0

queue는 변수 3개를 넣고있는데 vst배열에서 방문체크를 할때는 변수2개로 체크를 하고 있네요.

vst배열을 3차원으로 바꿔야 할 것 같습니다.

gi5005 3년 전 0

마지막 변수가 queue에서 F 큰순으로 queue에서 빠져나오는데 이미 힘이 더 많을때 방문했으면 그다음 방문하는건 의미가 없는거 아닌가요?

newdeal 3년 전 1

제가 잘못생각했었네요. 확인해보니까 2차원배열도 충분합니다. 제가봤을땐 가로와 세로변수가 혼용되기 때문인 것 같은데,

가로- H,sx,ex

세로-W,sy,ey

이렇게 입력을 받았는데 밑의 코드는 서로 섞여있는것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c++] bfs로 풀었는데 반레가 뭐가있을까요?

gi5005 3년 전 0

newdeal 3년 전 0

gi5005 3년 전 0

newdeal 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말