reiui9   1년 전

말이좀 헷갈려서

BFS 두가지방법으로 구현해봤는데 전부 틀렸다고 나오네요 ㅠ ㅠ

제가 케이스만들고 그려서 해봐도 자꾸틀렸다고...

도와주세요 ~

Nada   1년 전

3가지 문제점을 해결하니 정답이 나왔네요.

문제점들은 다음과 같습니다.


1. 우선 양방향 간선이 주어집니다.

따라서 Node[sc.nextInt()][sc.nextInt()] = 1이 아니라

int a = sc.nextInt(), b = sc.nextInt(); Node[a][b]=1; Node[b][a]=1

로 수정하셔야 합니다.


2. BFS부분에서 초기 start를 출력했음에도 check[초기 start] = 1을 해주는 과정이 없습니다.

때문에 초기 start를 while문 안에서 다시 한번 queue에 넣는 경우가 발생할 수 있습니다.


3. priority_queue 사용의 문제점

편의상 BFS를 탐색했을 때 (NODE 번호, 깊이)를 한 데이터라 가정하고

BFS의 특징은 깊이가 작은 것부터 순차적으로 접근해 나가야 합니다.

하지만 priority_queue를 사용했을 경우

( NODE 번호 = 2, depth = 3 ) , ( NODE 번호 = 1, depth = 4 ) 일 경우 어떤 것이 먼저 POP이 될까요?

깊이가 4이지만 NODE 번호가 작은 1번 노드가 먼저 나오게 됩니다.

따라서 이 때부터 BFS 탐색이 되지 못하게 됩니다.

때문에 priority_queue 대신에 그냥 queue를 사용하시면 해결됩니다.


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