[백준] Silver II. 트리의 부모 찾기

 

 

 

사용 알고리즘

• 그래프 탐색
• BFS

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int n;
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean [] visited;
    static int [] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        for(int i = 0; i <= n; i++){
            graph.add(new ArrayList<>());
        }
        visited = new boolean[n + 1];
        parent = new int[n+1];
        for(int i = 0; i < n -1 ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        bfs(1);

        for(int i = 2; i < parent.length; i++){
            System.out.println(parent[i]);
        }
    }

    public static void bfs(int start) {
        visited[start] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while(!queue.isEmpty()){
            int node = queue.poll();
            for(int next : graph.get(node)){
                if (visited[next]) continue;
                queue.add(next);
                visited[next] = true;
                parent[next] = node;
            }
        }
    }
}

 

회고

 

7
1 6
6 3
3 5
4 1
2 4
4 7

 

이 예제를 그래프로 나타내면

1 -- 6 -- 3 -- 5
 \
  \ 
   4 -- 2
   |
   |
   7

이런형태로 될 것이다.

2번 노드의 부모는 4,

3번은 6,

4번은 1

...

 

이런식으로 부모의 노드를 찾는 문제였다. 처음에 직관적으로 와닿지 않았는데, 각 노드와 연결된 노드를 출력해보니 이해가 되었다.

node: 1 next: 6 node: 1 next: 4
node: 6 next: 3
node: 4 next: 2 node: 4 next: 7
node: 3 next: 5

 

4번과 6번의 부모는 1

3번의 부모는 6

2번과 7번의 부모는 4

5번의 부모는 3

 

parent[next] = node;

이렇게 해당 노드들에 대해서 부모값을 저장하면 쉽게 풀리는 문제였다.