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

11725 트리의 부모찾기

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

문제설명

주어진 트리에서 루트 노드(1번 노드)부터 시작하여 각 노드의 부모를 찾는 문제다.

트리의 노드는 1번부터 N번까지 있으며, 트리는 사이클이 없는 연결된 그래프이다.

접근방식

O(n) 선형 시간복잡도

• 그래프 구축: O(N)
• BFS 탐색: O(N)
• 결과 출력: O(N)

 트리 구조에서 노드의 수가 많더라도 모든 작업이 선형 시간 내에 수행된다.

 

문제 조건 분석 과정

 

1. 첫 번째 줄에서 노드의 개수 N을 읽고, 다음 N−1 줄에서 간선 정보를 읽어 인접 리스트를 구축

2. 루트 노드(1번)의 부모는 0으로 설정하고 나머지는 -1로 초기화

3. 큐를 사용하여 너비 우선 탐색(BFS)을 수행

4. 현재 노드에서 방문하지 않은 이웃 노드를 발견하면, 해당 노드의 부모를 현재 노드로 설정하고 큐에 추가

전체코드

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

public class Main_11725트리 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //노드의 개수

        //인접 리스트 배열
        List<Integer>[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        //그래프 구축
        for (int i = 0; i < N - 1; i++) {
            String[] input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            graph[u].add(v); //노드 u에 인접한 v 추가
            graph[v].add(u); //노드 v에 인접한 u 추가
        }

        //부모 노드 저장하는 배열
        int[] parents = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parents[i] = -1; //부모가 없음 = -1
        }

        //BFS를 처리할 큐
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1); //노드 1
        parents[1] = 0; //노드 1의 부모 = 0

        //BFS탐색 시작
        while (!queue.isEmpty()) {
            int current = queue.poll(); //현재 노드 꺼냄
            for (int neighbor : graph[current]) { //현재 노드의 모든 이웃 탐색
                if (parents[neighbor] == -1) { //이웃 노드가 없는 경우
                    parents[neighbor] = current; //현재 노드 = 이웃 노드의 부모
                    queue.add(neighbor); //이웃 노드를 큐에 추가
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        //2 ~ N번 노드의 부모 출력
        for (int i = 2; i <= N; i++) {
            sb.append(parents[i]).append('\n');
        }
        System.out.print(sb.toString());
    }
}