[랜덤 마라톤] 트리의 부모 찾기(11725)

1. 문제 풀이 아이디어

• 그래프 탐색 기법(BFS)을 활용하여 문제를 해결한다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        int[] result = new int[n + 1];
        List<Integer>[] list = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int a = Integer.parseInt(stringTokenizer.nextToken());
            int b = Integer.parseInt(stringTokenizer.nextToken());
            list[a].add(b);
            list[b].add(a);
        }
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(1);
        visited[1] = true;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i = 0; i < list[cur].size(); i++) {
                if (visited[list[cur].get(i)]) continue;
                result[list[cur].get(i)] = cur;
                visited[list[cur].get(i)] = true;
                queue.add(list[cur].get(i));
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            stringBuilder.append(result[i]).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• n + 1 크기의 배열 result와 list를 초기화한다.

• n - 1번의 입력을 통해 각 노드 간의 간선 정보를 list 배열에 저장한다.

• 큐를 사용하여 BFS 탐색을 진행한다.

• 각 노드를 방문할 때, 해당 노드의 부모 노드인 cur을 result 배열에 저장한다.

• BFS가 끝난 후 result 배열을 2번 노드부터 출력하여 문제를 해결한다.