[백준] 11725번 : 트리의 부모 찾기 - 자바[Java]

11725번: 트리의 부모 찾기

풀이

트리라고 해서 트리 구조를 만들어야 하나? 라고 생각할 수도 있는데, 그래프를 그려서 해결할 수 있다.

 

인접 리스트로 그래프의 정보를 저장하고, 루트 노드에서부터 DFS또는 BFS로 탐색을 시작하여 아직 방문하지 않은 노드를 찾을 때마다 부모 노드 저장 배열(parent)에 부모 노드 번호를 저장하면 된다.

코드

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

public class Main {

    static int[] parent; //부모 노드 저장 배열

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>());
        parent = new int[n+1];

        StringTokenizer st;

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

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

        bfs(graph, n);

        for (int i = 2; i <= n; i++)
            System.out.println(parent[i]);
    }

    static void bfs(ArrayList<ArrayList<Integer>> graph, int n) {
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        boolean[] visited = new boolean[n+1];
        visited[1] = true;

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int vertex : graph.get(cur)) {
                if (!visited[vertex]) {
                    parent[vertex] = cur;
                    visited[vertex] = true;
                    q.add(vertex);
                }
            }
        }

    }

}