11725번 : 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 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.*;

public class Main {
    static int n;
    static int[] parent;
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        parent = new int[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < n + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            list.get(a).add(b);
            list.get(b).add(a);
        }

        dfs(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i < n + 1; i++) sb.append(parent[i] + "\n");
        System.out.println(sb);
    }
    
    static void dfs(int x) {
        if(visited[x]) return;
        visited[x] = true;
        for (int i = 0; i < list.get(x).size(); i++) {
            if(!visited[list.get(x).get(i)]) {
                parent[list.get(x).get(i)] = x;
                dfs(list.get(x).get(i));
            }
        }
    }
}

 

해결방법

처음에 문제 이해를 잘 못하였다. 단순히 두 번째 노드부터 n 번째 노드까지 각각의 루트 노드를 출력하는 문제이다.

일단 입력받은 노드들을 다 연결시켜 준다.

모든 노드들의 최상위 노드는 첫 번째 노드이므로 첫 번째 노드로 dfs를 실행해 주면 모든 노드들을 탐색하게 된다. 이때, 각각의 노드를 dfs 호출한 노드가 해당 노드의 루트 노드이므로 이를 parent 배열에 저장시킨 뒤 출력해 주면 해결할 수 있다.