[BFS] 백준 - 11725번: 트리의 부모 찾기 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

11725번: 트리의 부모 찾기

 

BFS로 두 번째 풀어보는 문제다!

DFS를 공부해둔 후 BFS에 접근해보니 생각보다 괜찮은 거 같았다. (물론 이 문제는 실버 2)

 

문제의 내용은 다음과 같다.

루트 노트는 무조건 1이고

각 노드들의 부모는 누구인지 프린트하는 것이다.

 

코드

import java.util.*;

public class Main {
    static ArrayList<Integer>[] map;
    static boolean[] visit;
    static int n;
    static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        map = new ArrayList[n];
        visit = new boolean[n];
        parent = new int[n];

        for (int i = 0; i < n; i++) {
            map[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;

            map[a].add(b);
            map[b].add(a);
        }

        bfs(0);

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

    private static void bfs(int start) {
        visit[start] = true;
        Queue<Integer> q = new LinkedList<>();
        q.add(start);

        while (!q.isEmpty()) {
            int num = q.remove();

            for (int i = 0; i < map[num].size(); i++) {
                if (!visit[map[num].get(i)]) {
                    visit[map[num].get(i)] = true;
                    q.add(map[num].get(i));
                    parent[map[num].get(i)] = num + 1;
                }
            }
        }
    }
}

채점하는 데 오래 걸려서 조마조마했다.

하지만 맞았으니 패스!