[백준/JAVA] 11725번: 트리의 부모찾기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static ArrayList<Integer> list[];
    static StringTokenizer st;
    static boolean[] isVisit;
    static int[] parentNode;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        isVisit = new boolean[N + 1];
		list = new ArrayList[N + 1];
		parentNode = new int[N + 1];

        // 초기화 
        for(int i = 0; i < N+1; i++){
            list[i] = new ArrayList<>();
        }

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

            list[a].add(b);  
            list[b].add(a); 
            // list[1] -> [6, 4]
            // list[2] -> [4]
            // list[3] -> [6, 5]
            // list[4] -> [1, 2, 7]
            // list[5] -> [3]
            // list[6] -> [1, 3]
            // list[7] -> [4]
        }

        dfs(1);

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

    private static void dfs(int i) {
        isVisit[i] = true; // isVisit[6] = t

        for(int a : list[i]){ // 1, 3
            if(!isVisit[a]) {
                parentNode[a] = i;  // parentNode[6] = 1  
                dfs(a); // dfs(6) // parentNode[3] = 6
            }
        }

    }

}

dfs 함수 호출: dfs(1)

dfs(1);은 트리의 루트 노드인 1번 노드에서 DFS(깊이 우선 탐색)를 시작하겠다는 의미입니다. 이 함수는 재귀적으로 호출되어 트리의 모든 노드를 방문하며 각 노드의 부모 노드를 찾습니다.

    1
   / \
  6   4
 /   / \
3   2   7
 \
  5

 

이제 dfs(1)이 호출되면 다음과 같은 순서로 노드를 방문하고 부모 노드를 설정합니다.

1. dfs(1)이 호출되면, 노드 1을 방문합니다 (isVisit[1] = true).
   • 1과 연결된 노드 6과 4를 검사합니다.
2. dfs(6)을 호출합니다 (isVisit[6] = true).
   • 6과 연결된 노드 1과 3을 검사합니다.
   • 노드 1은 이미 방문했으므로 넘어갑니다.
   • dfs(3)을 호출합니다 (isVisit[3] = true).
     • 3과 연결된 노드 6과 5를 검사합니다.
     • 노드 6은 이미 방문했으므로 넘어갑니다.
     • dfs(5)을 호출합니다 (isVisit[5] = true).
       • 5과 연결된 노드 3을 검사합니다.
       • 노드 3은 이미 방문했으므로 넘어갑니다.
     • dfs(5) 종료, parentNode[5] = 3.
   • dfs(3) 종료, parentNode[3] = 6.
3. dfs(6) 종료, parentNode[6] = 1.
4. 이제 dfs(4)를 호출합니다 (isVisit[4] = true).
   • 4과 연결된 노드 1, 2, 7을 검사합니다.
   • 노드 1은 이미 방문했으므로 넘어갑니다.
   • dfs(2)을 호출합니다 (isVisit[2] = true).
     • 2과 연결된 노드 4를 검사합니다.
     • 노드 4는 이미 방문했으므로 넘어갑니다.
   • dfs(2) 종료, parentNode[2] = 4.
   • dfs(7)을 호출합니다 (isVisit[7] = true).
     • 7과 연결된 노드 4를 검사합니다.
     • 노드 4는 이미 방문했으므로 넘어갑니다.
   • dfs(7) 종료, parentNode[7] = 4.
5. dfs(4) 종료, parentNode[4] = 1.