[백준 알고리즘] 11725번 자바(Java) 트리의 부모 찾기

조건

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

풀이

이문제의 핵심은 부모가 표시되지않은 2개의 연결 노드를 어떻게 표현할 것인가 다.

처음에 arr[N][N] 도 생각해서 표시를 해볼까 했지만 N의 최대값이 10만이기에 메모리 초과가 난다.

따라서 이중 배열리스트를 이용하여 두개의 값 연결을 표현해봤다. 이후 BFS를 통해 

자식 노드를 찾고 찾은 자식노드의 부모를 앞선 값으로 입력하도록 코드를 짰다.

참고로 이문제 알아두어야할점은 트리가 1개가 아니다. 아래처럼 말이다.

 

 

 

 

예제 입력 예시

7
1 6
6 3
3 5
4 1
2 4
4 7

 

예제 출력 예시

4
6
1
3
1
4

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//11725번 트리의 부모 찾기

public class P11725 {
    static boolean[] visited;
    static int[] parent;
    static ArrayList<ArrayList<Integer>> arrayList;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        visited = new boolean[N+1];
        parent = new int[N+1];
        arrayList = new ArrayList<>();
        for (int i = 0; i <=N; i++) {
            arrayList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < N-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            arrayList.get(num1).add(num2);
            arrayList.get(num2).add(num1);
        }

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

    static void bfs(int start){
        Queue<Integer> queue = new LinkedList<>();
        visited[start]= true;
        queue.add(start);
        while(!queue.isEmpty()){
            int cur = queue.poll();
            for (int i = 0; i < arrayList.get(cur).size(); i++) {
                if(!visited[arrayList.get(cur).get(i)]){
                    queue.add(arrayList.get(cur).get(i));
                    parent[arrayList.get(cur).get(i)] = cur;
                    visited[arrayList.get(cur).get(i)] = true;
                }
            }
        }
    }
}

 

 

 

 

문제 출처

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

11725번: 트리의 부모 찾기