[백준] 11725번 : 트리의 부모 찾기 – JAVA [자바]

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

 

 

 

---

문제

 

 

---

해결 방법

이 문제는 루트 없는 트리에서 각 노드의 부모를 찾는 문제이다. BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)을 활용하여 해결할 수 있다.

1. 그래프 구성
입력으로 주어진 트리의 연결 정보를 이용하여 인접 리스트를 만든다.
각 노드는 서로 연결된 상태이며, 양방향 간선으로 주어진다.

2. BFS를 이용한 부모 노드 찾기
BFS(너비 우선 탐색) 방법을 사용한다.
루트 노드(1번 노드)부터 탐색을 시작하며, 자식 노드들의 부모를 기록한다.
방문한 노드는 다시 방문하지 않도록 한다.

3. 결과 출력
2번 노드부터 N번 노드까지의 부모를 순서대로 출력한다.

 

 

---

코드 

 

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

public class Main {
    static List<Integer>[] tree;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n+1];
        parent = new int[n+1];

        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            tree[a].add(b);
            tree[b].add(a);
        }

        bfs(1);
        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            sb.append(parent[i]).append("\n");
        }
        System.out.print(sb);
    }

    public static void bfs(int root) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int i : tree[current]) {
                if (parent[i] == 0) {
                    parent[i] = current;
                    queue.add(i);
                }
            }
        }
    }
}

 

 

---

코드 설명

1. 그래프 구성
tree 리스트 배열을 이용하여 트리를 표현한다.
입력받은 간선을 양방향으로 저장한다.

2. BFS 탐색을 이용한 부모 노드 찾기
루트 노드를 1로 설정하고 BFS 탐색을 수행한다.
자식 노드를 방문할 때 부모를 기록한다.

 

 

---

시간 복잡도 분석

1. 그래프 생성: O(N)
2. BFS 탐색: O(N)

 

→ queue.poll()을 통해 각 노드를 한 번씩만 방문한다.
→ 노드가 N개이므로, 최악의 경우에도 O(N)번의 방문이 이루어진다.

→ 트리는 N-1개의 간선으로 이루어져 있으며, for (int i : tree[current])에서 각 간선을 최대 두 번(양방향 탐색) 탐색한다.
→ 따라서 간선 탐색에 대한 시간 복잡도는 O(N)이 된다.

종합 시간 복잡도: O(N)