[BOJ/백준] 11725 트리의 부모 찾기 (S2)

문제

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

풀이

해당 문제는 루트 없는 트리에서 각 노드의 부모를 찾아야 한다. 트리의 루트를 1로 정했을 때, 각 노드의 부모를 구하여 출력해야 한다.

 

우선 노드의 개수인 N을 입력받고, 이후 N-1개의 줄에서 두 노드의 연결 정보를 인접 리스트 구조로 입력는다.

그리고 DFS를 시작하여 루트 노드(1)를 방문 처리하고, 연결된 모든 노드를 탐색하면서 각 노드의 부모 노드를 찾는다. DFS는 재귀적으로 호출되며, 현재 노드를 방문 처리하고, 연결된 노드 중 방문하지 않은 노드를 탐색하면서 부모 노드를 설정한다. 모든 노드의 부모를 찾은 후, 2번 노드부터 순서대로 부모 노드를 출력한다. 

Code

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static List<List<Integer>> adjList;  // 인접 리스트
    static boolean[] visited;
    static int[] parents;  // 부모

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        adjList = new ArrayList<>();  // 인접 리스트 생성
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }
        visited = new boolean[N + 1];
        parents = new int[N + 1];

        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());
            adjList.get(a).add(b);
            adjList.get(b).add(a);
        }

        dfs(1); // 루트 노드를 1로 설정하고 시작

        for (int i = 2; i <= N; i++) {
            bw.write(parents[i] + "\n");
        }
        bw.flush(); bw.close();
    }

    private static void dfs(int now) {
        visited[now] = true;  // 현재 노드를 방문 처리

        // 인접 리스트 순회
        for (int node : adjList.get(now)) {
            if (!visited[node]) {  // 방문하지 않은 노드라면?
                parents[node] = now;  // 인접 노드의 부모를 현재 노드로 설정하고
                dfs(node);// 인점 노드 방문
            }
        }
    }
}