[트리#2] 백준 11725번: 트리의 부모 찾기 JAVA

11725번: 트리의 부모 찾기

문제

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

 

 

입력

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

 

 

출력

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

 

 

예제입출력

 

 

풀이

 이번 문제는 문제의 제목이 트리라고 해서 이진트리로 접근하였다. 그래서 괜히 코드만 복잡해지게 되고, 코드를 짜면 짤수록 코드만 복잡해지고 잘못접근하고 있다고 느꼈다. 알고보니 문제에서 꼭 이진트리라고 확정지은 것도 아닌데 이진트리로 접근하고 있었던 것이다. 트리도 일종의 그래프 형태이기 때문에 그래프로 접근하면 쉽게 문제를 해결할 수 있다. 물론 해당 노드의 부모를 찾는 로직을 고려해야한다. 그래프관련 개념은 아래 주소를 참조.

[#2] 그래프 이론(dfs와bfs) (tistory.com)

[#2] 그래프 이론(dfs와bfs)

 

 

소스코드

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

public class Tree2_11725 {

    static List<List<Integer>> graph;
    static int[] parents;
    static boolean[] visited;

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


        int n = Integer.parseInt(br.readLine());

        graph = new ArrayList<>();
        parents = new int[n+1];
        visited = new boolean[n+1];
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        StringTokenizer st;
        int a, b;
        for(int i=0; i<n-1;i++){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        bfs(1);
        for (int i = 2; i < parents.length; i++) {
            bw.write(parents[i]+" \n");
        }
        bw.flush();
        bw.close();

    }

    static void bfs(int data) {
        visited[data] = true;
        Queue<Integer> q = new LinkedList<>();
        q.offer(data);

        while (!q.isEmpty()) {
            int num = q.poll(); //부모 노드

            List<Integer> list = graph.get(num);
            for (int i = 0; i < list.size(); i++) {
                int temp = list.get(i);
                if (!visited[temp]) {
                    parents[temp] = num;
                    q.offer(temp);
                    visited[temp] = true;
                }
            }
        }
    }

}