[백준/BAEKJOON] 11725 : 트리의 부모 찾기 with Java

문제

루트 없는 트리가 주어진다. 이 때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

입력 예시 1

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

출력 예시 1

4
6
1
3
1
4

아이디어

BFS와 DFS 모두 사용하여 해결할 수 있는 문제입니다. 이번 문제에서는 BFS로 풀이 과정을 설명하겠습니다. 

 

첫 번째로 각 정점의 연결 상태를 어떻게 표현할지 고민해야 합니다. 우리는 배열을 사용하여 인접행렬을 만들 수도 있고, ArrayList를 중첩하여 각 정점에 연결된 정점들을 또 다른 ArrayList로 표현할 수 있습니다. 

 

저는 ArrayList를 구현하여 각 정점의 연결 상태를 구현하도록 하겠습니다. 

정점들의 연결 상태를 시각화

ArrayList를 중첩하여 연결 상태를 표현한다는 것은 위 그림과 같이 왼쪽에 정점이 있고 오른쪽에는 해당 정점과 연결되는 또 다른 정점들이 줄줄이 소세지 형태로 저장되어 있는 것을 의미합니다. 

 

입력 예시 1번을 토대로 저장된 상태를 표현해보면 이렇게 표현할 수 있습니다. 

 

1 → 6 4

2 → 4

3 → 6 5

4 → 1 2 7

5 → 3

6 → 1 3

7 → 4

하지만 이렇게 정점의 연결 상태가 정렬되지 않은 상태로 저장되었다면 우리는 무엇이 부모 정점이고 무엇이 자식 정점인지 어떻게 구별할 수 있을까요? 

 

이 때 BFS의 개념이 들어갑니다. BFS는 큐를 이용해 구현합니다. 

또한 우리는 각 정점의 부모 정점을 저장할 배열을 따로 선언해주어야 합니다. 

문제에서는 시작 정점을 1로 가정하고 있으므로, 우리는 1번 정점 부터 탐색을 시작하면 됩니다.

1

그 다음으로 큐에 들어간 정점을 제거하면서 해당 정점에 연결된 정점들을 큐에 삽입합니다

6

4

이 과정에서 우리는 하나의 조건문을 제시합니다. 

"만약 너네 부모가 선언 안되어 있으면 방금 제거된 정점을 너네 부모로 설정할게" 

int 형 배열은 선언과 동시에 0으로 초기화 됩니다. 즉, 따로 값을 집어 넣지 않은 상태의 디폴트(default) 값은 0이란 얘기입니다. 

따라서 만약 부모 정점을 확인하는 배열의 인덱스로 정점을 집어 넣었는데 0 이라면 해당 정점의 부모 정점이 저장되지 않았으므로 방금 제거 된 정점을 부모로 설정합니다. 

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

예를 들어, 방금 정점 1과 연결된 6과 4는 따로 부모 정점이 초기화 되지 않은 상태이므로 1이 저장되겠죠. 

해당 과정이 끝나면 큐에 있는 정점들을 또 빼내고 해당 정점과 연결된 정점들을 다시 큐에 삽입해줍니다. 이 때, 부모 정점이 있는 정점들은 다시 큐에 추가하지는 않습니다. 더 이상의 설명은 오히려 코드를 보면 쉽게 이해가 되실 수 있을겁니다.

코드

import java.util.*;

public class Main {
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>();
    static Queue<Integer> Queue = new LinkedList<>();
    static int [] parents;

    public static void BFS(){
        Queue.add(1); // 시작 정점을 큐에 삽입
        parents[1] = 1; // 정점에 1을 저장 (후에 조건문에 걸리지 않기 위해)

        while(!Queue.isEmpty()){
            int tmp = Queue.poll();
            for(int x : tree.get(tmp)){ // 큐에서 삭제된 정점의 연결 상태를 확인
                if(parents[x] == 0){ // 만약 부모 노드가 한번도 초기화 되지 않은 상태라면
                    parents[x] = tmp; // 부모 노드를 방금 삭제한 정점으로 저장하고
                    Queue.offer(x); // 새로 연결된 정점은 큐에 삽입
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        parents = new int[N+1]; // [1] 부터 [7] 까지 생성하기 위해 N+1
        for(int i = 0; i<N+1; i++){
            tree.add(new ArrayList<>()); // ArrayList의 중첩
        }

        for(int i = 0; i<N-1; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();

            //양방향으로 연결해준다
            tree.get(a).add(b);
            tree.get(b).add(a);
        }

        BFS();

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