[백준] 11725번 - 트리의 부모 찾기 (Silver 2)

문제 링크

백준 11725번 - 트리의 부모 찾기 (Silver 2)

문제 설명

간선들이 주어지고, 루트 노드를 1이라고 가정했을 때 각 노드의 부모 노드를 찾는 문제이다.

정답 코드 및 설명

각 노드마다 인접한 노드를 저장하는 연결리스트를 만들고, DFS를 수행하면서 부모를 찾는다.
DFS(Depth-First Search, 깊이 우선 탐색)은 노드의 자식을 탐색하는 과정을 계속 반복한다.
더 이상 내려가지 못하면 다시 올라와서 이웃한 노드를 탐색한다.
깊이 내려갔다가 다시 올라오는 식이라서 깊이 우선 탐색이라는 이름이 붙었다.

보통 재귀함수로 구현하게 되는데, 노드의 방문 여부를 확인해주지 않으면 무한 루프에 빠질 수 있다.
방문한 노드를 계속 다시 체크하는 경우가 발생할 수 있기 때문이다.

아래 코드에서는 인덱스를 좀 이상하게 구현해서 보기 힘들 수 있다.
$\textrm{connected}[i]$는 $i+1$ 노드의 인접한 노드들을 담고 있다.

다음에 비슷한 문제를 푼다면 인덱스를 좀 더 일관성 있게 구현해야겠다.
connected 배열의 크기를 1 크게 잡거나, 저장할 때 노드의 값을 전부 1씩 빼서 통일하는게 좋아보인다.

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

public class Main {

    static int parent[];
    static boolean check[];
    static ArrayList<Integer> connected[];

    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;
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        connected = new ArrayList[n];
        for (int i = 0; i < n; i++)
            connected[i] = new ArrayList<Integer>();
        parent = new int[n];
        check = new boolean[n];
        int e1, e2;
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            e1 = Integer.parseInt(st.nextToken());
            e2 = Integer.parseInt(st.nextToken());
            connected[e1 - 1].add(e2);
            connected[e2 - 1].add(e1);
        }
        findParent(1);
        for (int i = 1; i < n; i++)
            sb.append(parent[i]).append('\n');
        bw.write(sb.toString());
        bw.close();
    }

    // DFS 수행
    static void findParent(int node) {
        if (!check[node - 1]) {
            check[node - 1] = true;
            for (int j = 0; j < connected[node - 1].size(); j++) {
                int next = connected[node - 1].get(j);
                if (!check[next - 1]) {
                    parent[next - 1] = node;
                    findParent(next);
                }
            }
        }
    }
}