[백준/11725] - 트리의 부모 찾기(JAVA)

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

입력

---

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

출력

---

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

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static StringTokenizer st;
    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        arr = new ArrayList[T+1];
        parent = new int[T+1];
        visited = new boolean[T+1];
        for (int i = 1; i<T+1; i++){
            arr[i] = new ArrayList<>();
        }
        for (int i=0; i<T-1; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        //DFS
        DFS(1);

        // 출력
        for (int i=2; i<T+1; i++){
            System.out.println(parent[i]);
        }
    }
    static void DFS(int x){
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                parent[i] = x;
                DFS(i);
            }
        }
    }
}

해설

---

물론 전체적인 DFS 풀이의 기전은 비슷하지만, 여태까지 풀어본 DFS문제를 분류하라면, 크게 두개로 나눌 수 있다.

1. 전체 배열을 받아 연관관계를 찾고 영역의 개수 / 넓이를 찾는 문제

2. 일부 노드의 연관관계를 받아서 노드의 관계를 파악하는 문제

 

위의 문제는 2번에 속한다. 따라서 ArrayList<Integer>[] 배열을 이용함으로써 풀 수 있다.

    static StringTokenizer st;
    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int[] parent;

그래서 ArrayList와 visited, 그리고 노드의 부모를 구해야 하므로 parent 배열을 선언한다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        arr = new ArrayList[T+1];
        parent = new int[T+1];
        visited = new boolean[T+1];
        for (int i = 1; i<T+1; i++){
            arr[i] = new ArrayList<>();
        }
        for (int i=0; i<T-1; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        //DFS
        DFS(1);

        // 출력
        for (int i=2; i<T+1; i++){
            System.out.println(parent[i]);
        }
    }

ArrayList<Integer>[]같은 경우는 꼭 해줘야 할 것이, 선언한 후에 이를 초기화해주는 작업을 거쳐야 한다.

그리고 start와 end를 받아서 각 노드에 연결시켜준다.

예를 들어 4번 노드와 6번 노드가 연결되어 있다고 하면, 4번 노드에 6번을, 그리고 6번 노드에도 4번을 달아준다.

그리고 마지막으로 트리의 루트가 1이므로 DFS(1)을 실행시키고, 부모 노드의 리스트를 출력해주면 된다.

static void DFS(int x){
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                parent[i] = x;
                DFS(i);
            }
        }
    }

DFS 함수같은 경우에는 각 ArrayList를 돌면서 방문하지 않았던 노드에 대해서 parent배열에 기입한다.

이 부분이 이해가 안 되는 사람이 있을 것이다. 예를 들면서 확인해보자.

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

1번 노드를 최상단 노드라고 하였으므로, 관계를 나타내면 다음과 같다.

1                                                                  
├─4──2
| └──7
└─6──3──5

DFS를 실행하기 전에 ArrayList의 내용을 찍어보면 다음과 같다.

for (ArrayList<Integer> i : arr){
 System.out.println("i = " + i);
}
===========
i = null
i = [6, 4]
i = [4]
i = [6, 5]
i = [1, 2, 7]
i = [3]
i = [1, 3]
i = [4]

이제 DFS를 실행했을 때의 경과를 보자.

DFS(1)을 실행하면 visited[1] 배열이 true로 바뀌고,

1번 배열의 [6, 4]에 대해서 재귀함수를 실행할 것인지를 물어본다.

6으로 넘어가서, 방문하지 않았으므로 방문했다는 체크를 하고 6의 parent는 1로 표기해놓는다.

그리고 DFS(6)을 실시한다. 6번 배열에는 [1,3]이 있고, 1은 표기했으므로 실행하지 않고 3번 노드로 넘어가서 3번 노드의 부모를 6으로 체크한다.

후의 노드에 대해서 전부 체크한다.

이런 식으로 흘러가는 간단한 ArrayList<Integer>[] 배열의 문제였다.