[백준] 11725 트리의 부모 찾기 | DFS, BFS, 그래프 | 실버 Ⅱ | JAVA

📌 문제

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

 

⭐ 문제 해결을 위한 접근 방식

이 문제는 루트 없는 트리에서 각 노드의 부모를 찾는 문제입니다. 트리의 구조를 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)로 탐색하여 각 노드의 부모를 기록하면 됩니다.

알고리즘 설계

1. 입력 파싱: 주어진 입력을 읽어 그래프를 인접 리스트로 표현합니다.
2. 탐색:
   • 루트 노드(1번 노드)를 기준으로 BFS를 수행합니다.
   • 탐색 중 각 노드의 부모를 기록합니다.
3. 출력: 2번 노드부터 N번 노드까지의 부모를 출력합니다.

주요 고려 사항

• 입력 크기가 최대 100,000으로 탐색 알고리즘은 O(N)O(N)O(N) 복잡도를 가지는 방식(BFS/DFS)을 사용해야 효율적으로 처리할 수 있습니다.
• 양방향 그래프로 주어지기 때문에 방문 처리를 통해 중복 탐색을 방지합니다.

 

✅ 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        // 그래프 인접 리스트 초기화
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(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());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        // 부모를 기록할 배열
        int[] parent = new int[n + 1];
        boolean[] visited = new boolean[n + 1];

        // BFS를 이용해 부모 찾기
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        visited[1] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    visited[next] = true;
                    parent[next] = current;
                    queue.offer(next);
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            sb.append(parent[i]).append("\n");
        }
        System.out.print(sb);
    }
}

🗒️ 코드 풀이

1. 문제 이해

이 문제는 트리의 구조를 활용하여 루트 노드(1번 노드)를 기준으로 각 노드의 부모를 찾는 문제입니다. 트리는 사이클이 없는 연결 그래프이므로 BFS 또는 DFS를 사용해 탐색을 진행하며, 각 노드의 부모를 기록할 수 있습니다.

2. 입력 및 그래프 구성

입력된 트리의 간선 정보를 인접 리스트로 변환합니다. 이 과정에서 노드 aaa와 bbb 간의 양방향 간선을 저장합니다.

3. BFS를 이용한 탐색

1번 노드부터 BFS를 수행하며 각 노드의 부모를 parent 배열에 기록합니다. 방문 배열을 활용해 탐색 중복을 방지합니다.

4. 결과 출력

부모를 기록한 parent 배열을 사용하여 2번 노드부터 NNN번 노드까지의 부모를 출력합니다.

5. 시간 및 공간 복잡도

• 시간 복잡도: O(N)O(N)O(N) (그래프의 모든 노드를 한 번씩 방문)
• 공간 복잡도: O(N)O(N)O(N) (그래프 인접 리스트와 부모 배열 사용)

6. 코드 설명

• 그래프 초기화: 각 노드에 연결된 다른 노드를 인접 리스트로 저장합니다.
• BFS 탐색: 큐를 이용해 탐색하며 부모 노드를 기록합니다.
• 출력: 탐색 완료 후 2번 노드부터 부모 노드를 출력합니다.