글 읽기 - BFS에서 return값에 따라 정답/오답이 달라지는데 이유를 잘 모르겠습니다.

imspecialone 4년 전 0

안녕하세요

BFS로 해결했는데, 53번 line의 return Distance+1을 54번line의 return Distance로 바꾸면 오답이 됩니다.

그런데 문제에서 도착점에 도착하지 못하는 경우는 없다고 했으니,

입력이 어떻게 들어오든 상관없이

1)반드시 while문 도중에 41번줄의 return Distance+1;로 이동해서 return되거나

2)혹은 route queue가 텅 빌때까지 돈 후 while문을 탈출하면, 54번 줄의 Distance는 최종적으로 41번줄의 Distance+1과 같아지므로 return Distance로 반환해도 정답이 되어야 할 것 같은데

왜 53번 line 처럼 작성하면 정답이고 54번 line 처럼 작성하면 오답인지 궁금합니다...

//의문점 : BFS의 return이 왜 Distance가 아니라 Distance+1인지
#include <iostream>
#include <queue>

using namespace std;

int N, M;
int **maze;
bool **visited;
int dx[] = {0,0,1,-1};
int dy[] = {-1,1,0,0};


int BFS(int y, int x,int Distance)
{
	//1. 현재 위치를 visited에 넣는다.
	visited[y][x] = true;
	//2. 현재 위치의 distance를 언제,어떻게 증가시켜야 할 지 결정해야 함
	//거리 큐를 만들어서 넣자 (O)
	//3.현재 위치와 거리를 큐에 넣는다.
	queue<pair<int, int>> route;
    queue<int> distanceQue;
    
	route.push(make_pair(y, x));
	distanceQue.push(Distance);

	do {
		y = route.front().first;
		x = route.front().second;
		Distance = distanceQue.front();
		route.pop();
		distanceQue.pop();
		//현재 위치 주변의 4점을 탐색한다.
		for (int i = 0; i < 4; ++i){
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if (nx >= 0 && nx < M && ny >= 0 && ny < N)//4점 보드안에 위치한지 검사
			{
				if (ny == N - 1 && nx == M - 1) //도착점이면 바로 반환
					return Distance+1;
				if (visited[ny][nx] == false && maze[ny][nx] == 1) 
				{
					//4. 방문하지 않은 경우 방문처리
					visited[ny][nx] = true;
					//5. 큐에 넣기
					route.push(make_pair(ny, nx));
					distanceQue.push(Distance+1);
				}
			}
		}
	} while (!route.empty());
	return Distance + 1;//왜 Distance가 아니라 Distance+1일까?
	//return Distance; <--오답
}

int main()
{
	scanf("%d %d", &N, &M);

	maze = new int*[N];
	for (int i = 0; i < N; ++i)
		maze[i] = new int[M]();

	visited = new bool*[N];
	for (int i = 0; i < N; ++i)
		visited[i] = new bool[M]();

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			scanf("%1d", &maze[i][j]);

	cout << BFS(0, 0, 1);
}

wjsqjawns 4년 전 2

반례입니다.

sait2000 4년 전 1

http://boj.kr/525bba2ad1df471b...

+1 하든 안하든 둘 다 맞습니다 아마도. 위에 반례는 데이터가 틀렸습니다.

wjsqjawns 4년 전 0

@sait2000 지적 감사합니다. 저 당시에 저걸 반례라고 올린 제가 이해가 안 되네요. 반성합니다....

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

문제

문제

출처

ICPC

BFS에서 return값에 따라 정답/오답이 달라지는데 이유를 잘 모르겠습니다.

imspecialone 4년 전 0

wjsqjawns 4년 전 2

sait2000 4년 전 1

wjsqjawns 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말