글 읽기 - 2178번 미로문제 소스 차이좀 봐주세요

qkrqudwn12 8년 전 0

아래 두코드에 이부분이라고 써놨습니다. 아래코드로 하면 되나 위코드로 하면 틀렸다고 되는데

아무리 생각해봐도 문제가 되지않을것 같은데 과연 무엇일까요 ㅠ enque해서 체크하나 deque하고 check하나

고수님들 도와주십쇼

public static void bfs(int x, int y, int dx, int dy) {
		enque(x, y);
		while (!empty()) {
			int fx = dequex();
			int fy = dequey();
            bool[fx][fy]=true; << 이부분
			if (fx == dx && fy == dy) {
				if (result == 0)
					result = array[dx][dy];
				else if (result > array[dx][dy])
					result = array[dx][dy];
				
			}
			for (int i = 0; i < 4; i++) {
				if (fx + rl[i] >= 1 && fx + rl[i] <= h && fy + ud[i] >= 1 && fy + ud[i] <= w) {
					if (bool[fx + rl[i]][fy + ud[i]] == false) {
						if (array[fx + rl[i]][fy + ud[i]] == 1 || array[fx + rl[i]][fy + ud[i]] > array[fx][fy]) {
							array[fx + rl[i]][fy + ud[i]] = array[fx][fy] + 1; 
							enque(fx + rl[i], fy + ud[i]);
						}
					}
				}

			}

		}
	}


public static void bfs(int x, int y, int dx, int dy) {
		enque(x, y);
		bool[x][y] = true;
		while (!empty()) {
			int fx = dequex();
			int fy = dequey();
			if (fx == dx && fy == dy) {
				if (result == 0)
					result = array[dx][dy];
				else if (result > array[dx][dy])
					result = array[dx][dy];
				
			}
			for (int i = 0; i < 4; i++) {
				if (fx + rl[i] >= 1 && fx + rl[i] <= h && fy + ud[i] >= 1 && fy + ud[i] <= w) {
					if (bool[fx + rl[i]][fy + ud[i]] == false) {
						if (array[fx + rl[i]][fy + ud[i]] == 1 || array[fx + rl[i]][fy + ud[i]] > array[fx][fy]) {
							array[fx + rl[i]][fy + ud[i]] = array[fx][fy] + 1;
							bool[fx + rl[i]][fy + ud[i]] = true;  << 이부분
							enque(fx + rl[i], fy + ud[i]);
						}
					}
				}

			}

		}
	}

orange4glace 8년 전 1

풀 소스가 없어 명확히 설명드리긴 어렵습니다만,

queue에서 뺄 때 visit를 체크하게 되면

0, 0에서 출발했을 때

step 0일 때(0, 0)

step 1일 때 큐에 (1, 0), (0, 1)

그럼 step 2일때는 큐에 1, 1이 2번 중복해서 들어가게 되는 문제가 생길 것같습니다.

qkrqudwn12 8년 전 0

아아! 감사합니다 !!

baactree 8년 전 1

일반적으로 dfs 진입할때 방문체크 bfs 큐에 넣을때 방문체크

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

문제

문제

출처

ICPC

2178번 미로문제 소스 차이좀 봐주세요

qkrqudwn12 8년 전 0

orange4glace 8년 전 1

qkrqudwn12 8년 전 0

baactree 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말