[BOJ] 11725 - 트리의 부모 찾기 JAVA

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

문제

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

입력

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

출력

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

예제 입력 1

7

1 6

6 3

3 5

4 1

2 4

4 7

예제 출력 1

4

6

1

3

1

4

예제 입력 2

12

1 2

1 3

2 4

3 5

3 6

4 7

4 8

5 9

5 1

0 6

11

6 12

예제 출력 2

1

1

2

3

3

4

4

5

5

6

6

 

 

 

 

 

 

풀이 .

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<Integer>[] map = null;
    static int[] parent = null;
    static boolean[] check = null;

    public static void dfs(int node) {
        for(int next : map[node]) {
            if(!check[next]) {
                check[next] = true;
                parent[next] = node;
                dfs(next);
            }
        }
    }

    public static void bfs(int root) {
        Queue<Integer> que = new ArrayDeque<>();
        que.add(root);
        check[root] = true;

        while(!que.isEmpty()) {
            int now = que.poll();
            for(int next : map[now]) {
                if(!check[next]) {
                    check[next] = true;
                    parent[next] = now;
                    que.add(next);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        map = new ArrayList[n + 1];
        parent = new int[n + 1];
        check = new boolean[n + 1];
        for(int i = 1; i <= n; i++) {
            map[i] = 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());
            map[u].add(v);
            map[v].add(u);
        }

//        dfs(1); check[1] = true;
        bfs(1);
        for(int i = 2; i <= n; i++) {
            sb.append(parent[i] + "\n");
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

 

DFS, BFS 를 사용해 트리의 탐색을 할 수 있다.

(트리도 그래프이다. 사이클이 없으며 반드시 모든 노드가 연결된 그래프.)

 

int[] parent를 사용해 탐색을 진행하며 각 노드의 부모노드를 알아낼 수 있다.

(루트를 제외한 모든 노드는 하나의 부모만을 갖기 때문에 next로 넘어가기 전 노드인 now가 next의 노드가 된다.)