[BOJ][Java] 11725번 트리의 부모 찾기

문제 설명

문제 링크 : https://www.acmicpc.net/problem/11725

 

이 문제는 트리를 구현하는 기본적인 문제이다.

루트노드가 1번으로 고정되어 있기 때문에 

그저 양방향 인접 리스트로 그래프를 표현하고

1번 노드부터 탐색하며 부모노드를 찾아주면 된다.

 

예제 입력 1번을 그래프로 표현하면 위와 같다.

여기서 루트노드가 1번이기 때문에 루트노드부터 시작해서

4번 노드의 부모는 1번, 6번 노드의 부모는 1번

2번 노드의 부모는 4번, 7번 노드의 부모는 4번

이런 식으로 순차적으로 부모를 찾아주면 된다.

이 과정에서는 DFS나 BFS를 사용하면 된다.

 

그래프를 리스트로 표현할 때는 방향이 없는 간선이므로 

이와 같이 인접리스트로 표현해주면 된다.

 

package boj;

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

public class BOJ11725 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        List<List<Integer>> list = new ArrayList<>();
        boolean[] visited = new boolean[N+1];
        visited[1] = true;
        int[] parents = new int[N+1];
        Queue<Integer> q = new LinkedList<>();
        q.add(1);

        for(int i = 0; i <= N; i++){
            list.add(new ArrayList<>());
        }

        for(int i = 0; i < N-1; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            list.get(u).add(v);
            list.get(v).add(u);
        }

        while(!q.isEmpty()){
            int now = q.poll();
            for(int next: list.get(now)){
                if(!visited[next]){
                    visited[next] = true;
                    parents[next] = now;
                    q.add(next);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 2; i < parents.length; i++){
            sb.append(parents[i]).append("\n");
        }

        System.out.println(sb);
    }
}