zas777   1년 전

bfs로 해결하고 dfs로 해결하려는데 비슷하게 dfs형식으로 고치니까 틀렸다고 나오더 라고요..

50%에서요 어떤게 문제인가요??

wjsqjawns   1년 전

BFS와 DFS의 차이때문입니다.

해당 문제에서 바라는 것은, 출발지점으로부터 각 노드까지의 최단 거리입니다.

BFS는 너비 우선 탐색으로, BFS의 방문 순서는 가중치를 1로 두는 해당 문제에 알맞습니다.

하지만 DFS는 그렇지 않습니다.

간단하게 예를 들어보죠.

3 3

1 2

2 3

1 3

만약 위와 같은 입력이 들어오게 된다면, 1번 노드를 기준으로

BFS라면 2까지 거리가 1, 3까지 거리가 1입니다.

하지만 DFS라면 2(혹은 3)까지의 거리가 1이면, 3(혹은 2)까지의 거리는 2가 됩니다.

위의 코드는 방문 여부를 확인하므로, 값의 갱신도 이루어지지 않습니다.

이게 문제가 되어 틀리는 것 같네요.

zas777   1년 전

댓글 감사합니다.

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