[Java] BOJ 11725 트리의 부모 찾기

문제 

문제 링크 https://www.acmicpc.net/problem/11725

• 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
• 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
• 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

아이디어

• 인접 리스트로 트리를 구현해서 양방향으로 트리의 간선 정보를 입력받는다.
• 그리고 DFS로 노드마다 부모 노드를 찾아서 배열에 저장한다.
• 우선 루트를 1로 정했으므로, 1부터 DFS를 돌리며 노드 1을 방문처리하고, 1에 연결된 노드 중 방문 되지 않은 노드라면 해당 노드의 부모 노드를 1로 저장하고 (만약 1에 2라는 노드가 연결되어있었다면, parent[2] = 1이라 저장) 해당 노드로 DFS를 다시 돌린다.
• 다음 노드로 DFS를 돌릴 때도, 해당 노드를 방문처리하고 해당 노드와 연결된 노드들 중 방문 처리 되어있지 않은 노드라면, 그 노드의 부모를 현재 DFS를 돌리고 있는 노드로 저장하고 다시 DFS를 돌리며 반복한다.

겪은 시행착오

• X

트리 문제라서 어제처럼 클래스 만들어서 풀 줄 알았는데 생각보다 간단하게 풀려서 좋았다..!! 좀 더 트리를 열심히 공부해서 자연스럽게 풀 수 있는 그날까지...파이팅!!

코드

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

public class BOJ11725 {
    static int N;
    static ArrayList<Integer> tree[];
    static int parent[];
    static boolean visited[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());
        // 인접 리스트로 트리 구현
        tree = new ArrayList[N + 1];
        // 각 노드의 부모를 저장할 배열
        parent = new int[N + 1];
        // 방문 처리
        visited = new boolean[N + 1];

        // 인접 리스트 초기화
        for (int i = 1; i <= N; i++) {
            tree[i] = new ArrayList<>();
        }

        // 트리의 간선 정보 입력받기
        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 양방향으로 연결
            tree[a].add(b);
            tree[b].add(a);
        }

        // DFS를 통해 부모 정보 찾기 (루트 노드를 1부터 시작한다 했으므로)
        dfs(1);

        // 2번 노드부터 N번 노드까지의 부모 출력
        for (int i = 2; i <= N; i++) {
            sb.append(parent[i]).append("\n");
        }

        System.out.print(sb);
    }

    // 부모 노드 찾기 위한 DFS
    public static void dfs(int node) {
        // 현재 노드 방문 처리
        visited[node] = true;

        // 현재 노드와 연결된 자식 노드들 확인
        for (int child : tree[node]) {
            // 방문하지 않은 노드라면
            if (!visited[child]) {
                // 현재 노드를 해당 노드의 부모로 저장 후
                parent[child] = node;
                // 자식 노드로 다시 DFS를 돌림
                dfs(child);
            }
        }
    }
}