BOJ_11725 / 트리의 부모 찾기

📌 문제 탐색하기

• 입력:
  • 첫째 줄: 노드의 개수 N (2 ≤ N ≤ 100,000)
  • 둘째 줄부터 N-1개의 줄: 트리 상에서 연결된 두 정점이 주어진다.
• 출력:
  • 2번 노드부터 N번 노드까지 각 노드의 부모 노드 번호를 한 줄에 하나씩 출력한다.

---

📌 어떤 알고리즘?

• 그래프 탐색:
  • 트리는 사이클이 없는 연결 그래프
  • DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)으로 각 노드의 부모를 찾을 수 있다.

---

📌 코드 설계하기

1. 입력 처리:
   • N과 트리 간선 정보를 입력받아 인접 리스트로 트리를 표현한다.
   • visited[]: 각 노드 방문 여부를 기록한다.
   • parentNode[]: 각 노드의 부모 노드를 저장한다.
2. DFS 탐색:
   • 1번 노드를 루트로 설정하고 자식 노드를 탐색하며 부모를 저장한다.
3. 출력:
   • parentNode[2]부터 parentNode[N]까지 출력한다.

---

📌 정답 코드

package BOJ_11725;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_11725 {
    static int N;
    static List<List<Integer>> edgeList = new ArrayList<>();
    static boolean[] visited;
    static int[] parentNode;
    static StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bufferedReader.readLine());

        // 인접 리스트 초기화
        for (int i = 0; i <= N; i++) {
            edgeList.add(new ArrayList<>());
        }

        // 간선 정보 입력
        for (int i = 1; i < N; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            int front = Integer.parseInt(stringTokenizer.nextToken());
            int back = Integer.parseInt(stringTokenizer.nextToken());
            edgeList.get(front).add(back);
            edgeList.get(back).add(front);
        }

        // 배열 초기화
        visited = new boolean[N + 1];
        parentNode = new int[N + 1];

        // DFS로 부모 찾기
        dfs(1);

        // 결과 출력
        for (int i = 2; i <= N; i++) {
            stringBuilder.append(parentNode[i]).append('\\n');
        }
        System.out.print(stringBuilder);
    }

    private static void dfs(int startNode) {
        visited[startNode] = true;
        for (int child : edgeList.get(startNode)) {
            if (!visited[child]) {
                parentNode[child] = startNode; // 부모 저장
                dfs(child);
            }
        }
    }
}

---

📌 시간 복잡도?

• 시간 복잡도:
  • DFS는 각 노드와 간선을 한 번씩 방문하므로 O(N)
  • 인접 리스트 초기화와 탐색을 포함한 전체 시간 복잡도도 O(N)
• 공간 복잡도:
  • 인접 리스트와 방문 배열, 부모 배열이 필요하므로 O(N)