백준 No.24446 알고리즘 수업 - 너비 우선 탐색 3 - JAVA

 

 

문제

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비우선 탐색으로 만들어 지는 트리를 너비우선 탐색 트리라고 하자. 너비 우선 탐색 트리에 있는 모든 노드의 깊이(depth)를 출력하자. 시작 정점 R의 깊이는 0이고 방문 되지 않은 노드의 깊이는 01로 출력하자

 

 

 

문제에서 트리라는 표현을 이해 못해 계속 틀리고 억지로 맞췄는데 출력초과로 계속 틀렸다.... 

결국 이 문제는 자식노드를 다 같은 depth로 보고 풀어야 한다. 그렇기 때문에 일반적으로 bfs를 표현할 때 시작 점부터 큐에 담고 하나씩 뽑으면서 while(!q.isEmpty())를 돌리며 큐를 하나씩 뽑아 for문을 돌리는 형식에서 반복문이 한 개가 추가 되어야 풀 수 있다. 그리고 여기에 depth를 나타내는 배열도 추가로 만들어야 한다. 

 

 

이게 핵심코드인데 

1. BFS이므로 Queue를 선언한다. Queue<Integer> queue = new LinkedList<>();

2. Queue에 시작점으로 주어지는 R을 먼저 넣는다.

3. 가장 필요한 방문체크를 해야하기 때문에 visited배열을 만든다. 여기서 0은 쓰지 않고 1부터 사용하기에 크기를 1 늘린다.

4. 시작점은 방문한 곳이기에 방문처리 한다. 

5. dep은 depth배열에 들어갈 값이다 결국 트리에 깊이를 나타내는데 제일 처음 시작은 0이다.

6. 문제에서 방문하지 않은 곳은 -1 로 처리해야 한다하여 depth배열은 모두 -1로 변경한다.

7. while() 을 통해 queue가 빌 떄까지 반복한다.

8. 보통 여기서 for문 하나를 통해 poll을 하지만 트리형식으로 해야하기 때문에 반복문을 하나 더 돌린다. 반복문은 queue에 사이즈가 0이 될 떄까지 돌아야 한다. 

9. 반복문 안에서 poll을 하나씩  하며 queue에 값들을 꺼낸다. depth의 인덱스가 해당 그래프 값이다. 처음 시작한다면 poll 된 값은 시작값인 1이 들어올 것이고 1의 깊이는 0으로 지정된다. --> 시작 깊이는 0이다 (문제에서 주어짐)

10. 그러고 그래프 값 1과 연결된 그래프를 살펴본다 -> 인접리스트로 구현함 그렇게 for문을 한 번 더 돌리고 여기서 방문 처리를 하며 방문하지 않았다면 방문하면서 queue에 값을 넣는다. 이렇게 1이 가리킨 노드들은 전부 큐에 담은 상태로 외부 for문까지 나오게 된다. 그러고 다시

11. while문으로 가고 queue.에 값 두 개가 방금 전에 들어와서 다시 while문이 동작한다. 근데 여기서 dep은 +1 이 되었으므로 깊이로 보면 1 깊이로 들어오고 탐색을 이어나간다. 여기서 부터 7번부터 모두 방문하며 끝이난다. 

 

 

 

디버깅

입력값

5 5 1
1 4
1 2
2 3
2 4
3 4

 

7번부터 본다면

현재 시작인 1인 값이 queue에 담겨지고 visited도 방문처리가 되어있다. 

depth[qu] = dep 부분에서 depth에 1번이 0으로 변경된다. 

1번 노드와 연결된 노드 2번, 4번을 queue에 담고 방문처리한다. 그러고 depth가 +1증가할 것이다

이처럼 while문 안에 

해당 for문을 넣은 이유를 알 수 있다.  이 문제는 트리개념으로 봐야하기 때문에 queue에 들어간 값들이 가리키고 있는 노드들은 다 같은 깊이라고 봐야한다. 

이런식으로 이해하면 편하다 그리고 주어진 간선들을 조합하면

이 상태로 출력된다.

 

그림을 보고 다시 풀이를 보면

1. 1번 노드와 연결된 노드들이 queue에 담김 (2,4) - 2,4는 방문처리되고 1번 노드 깊이는 0으로 지정됨

2. 2, 4와 가리키고 있는 노드를 queue에 담음  -> 2먼저 for문에 들어옴 1, 4, 3 여기서 1과 4는 방문 했기에 3만 방문처리하고 queue에 담음 -> 4차례일 경우 1, 2 ,3  모두 방문 했던 곳이기에 통과 depth가 1로 지정(2,4)

3. queue에 담긴 3이 for문에 들어가지만 이미 모두 방문처리 되어 그냥 통과 그러고 dep은 2로 지정된다. 

4. 5번 노드도 주어지지만 간선이 없어서 그냥 -1이 출력된다.

 

2번 노드와 4번 노드가 연결된 게 가장 이해가 안 됐지만 방문처리를 통해 바로 알 수 있었다. 

 

 

참고

https://sujin7837.tistory.com/455

[Java] 백준 24446번 : 알고리즘 수업 - 너비 우선 탐색 3