[BOJ] 트리의 부모 찾기

문제

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

풀이

서로간의 노드간의 연결 상태를 List로 표현을 하였다.
즉, 1 2와 2 3이 주어졌으면
list[1]은 2, list[2]는 1와 3, list[3]은 2를 가지게 된다.

이때 각 리스트의 첫번째 인덱스들이 부모가 되는 것으로 알고 있었다.
그러나 다음과 같은 반례를 찾았다.

3
2 3
1 2

Answer
1
2

리스트의 첫번째 인덱스는 단순 처음에 연결된 정보이지 부모임을 보장할 수 없기 때문이다.

따라서 탐색을 수행해야 한다.

탐색하지 않은 곳을 기준으로 visited체크를 하면서 마지막 노드에 도달한다면 자식이 없다는 뜻이므로 start지점이 부모가 된 것을 알 수 있다.

이를 parents배열에 기억하여 출력해준다.

import java.lang.*;
import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List[] list = new List[N + 1];
        boolean[] visited = new boolean[N + 1];
        int[] parents = new int[N + 1];

        for(int i = 0; i < N - 1; i++) {
            int[] nodes = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            if (list[nodes[0]] == null) {
                list[nodes[0]] = new ArrayList<Integer>();
            }

            if (list[nodes[1]] == null) {
                list[nodes[1]] = new ArrayList<Integer>();
            }

            list[nodes[0]].add(nodes[1]);
            list[nodes[1]].add(nodes[0]);
        }

        dfs(1, parents, visited, list);

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

    }

    static void dfs(int start, int[] parents, boolean[] visited, List<Integer>[] list) {
        visited[start] = true;

        for(int num : list[start]) {
            if (!visited[num]) {
                dfs(num, parents, visited, list);
                parents[num] = start; 
            }
        }
    }
}

https://github.com/Win-9/Algorism/tree/main/BOJ/%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EB%B6%80%EB%AA%A8%20%EC%B0%BE%EA%B8%B0