11725번 트리의 부모 찾기

문제: 트리의 부모 찾기

• BFS로 해결할 수 있는 문제입니다.
• 인접 그래프로 트리를 저장한 뒤 루트 노드를 시작점으로 BFS로 순회를 합니다.
  • BFS 순회를 하면서 저장할 값은 {node: root, depth: 1} 입니다.
• 새로운 노드를 방문할 때 마다 새로운 노드와 기존에 방문한 노드 깊이 + 1을 큐에 넣어줍니다.
  • {node: newNode, depth: depth + 1}
• 루트부터 bfs를 한 번 돌면 모든 노드가 트리에서 가지고 있는 깊이를 알 수 있습니다.
• 루프를 N번 돌면서 각 노드의 인접 노드(부모 OR 자식) 중에 깊이가 작은 값이 자신의 부모노드입니다.

코드

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


public class Main {

    public static int N;
    public static List<Integer>[] graph;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        graph = new List[N];
        for (int i = 0; i < N; ++i) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; ++i) {
            String[] edgeInfo = br.readLine().split(" ");

            int n1 = Integer.parseInt(edgeInfo[0]);
            int n2 = Integer.parseInt(edgeInfo[1]);

            n1--; n2--;

            graph[n1].add(n2);
            graph[n2].add(n1);
        }

        //bfs
        int[] depths = bfs(0);

        //result
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < N; ++i) {
            int parentDepth = Integer.MAX_VALUE;
            int parent = -1;
            for (int adjNode : graph[i]) {
                int adjDepth = depths[adjNode];
                if (adjDepth < parentDepth) {
                    parentDepth = adjDepth;
                    parent = adjNode;
                }
            }

            sb.append(parent + 1);
            sb.append('\n');
        }

        System.out.println(sb);
    }

    public static int[] bfs(int node) {
        int[] depths = new int[N];
        boolean[] visited = new boolean[N];

        Queue<Integer[]> q = new LinkedList<>();

        q.add(new Integer[]{node,1});
        depths[node] = 1;
        visited[node] = true;

        while (!q.isEmpty()) {
            Integer[] now = q.poll();
            int nowNode = now[0];
            int nowDepth = now[1];

            for (int nxt : graph[nowNode]) {
                if (!visited[nxt]) {
                    visited[nxt] = true;
                    q.add(new Integer[]{nxt, nowDepth + 1});
                    depths[nxt] = nowDepth + 1;
                }
            }
        }

        return depths;
    }
}