트리의 부모 찾기

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초 256 MB 27396 11727 8664 42.697%

문제

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

입력

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

출력

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

예제 입력 1

7 1 6 6 3 3 5 4 1 2 4 4 7

예제 출력 1

4 6 1 3 1 4

예제 입력 2

12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12

예제 출력 2

1 1 2 3 3 4 4 5 5 6 6

출처

문제를 만든 사람: baekjoon

잘못된 조건을 찾은 사람: jh05013

알고리즘 분류

그래프 이론

그래프 탐색

트리

너비 우선 탐색

깊이 우선 탐색

풀이 방법

bfs 방법을 이용해서 풀었다. 방향이 없이 연결되어 있기 때문에 Arraylist배열인 lists를 이용해서 양쪽을 전부 나타내 주었다.

1을 루트로 하기 때문에 queue에 먼저 넣어서 bfs로 찾아갔다.

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        boolean[] check = new boolean[n];
        List<Integer>[] lists = new ArrayList[n];
        int[] parent = new int[n];

        for (int i = 0; i < lists.length; i++) {
            lists[i] = new ArrayList<>();
        }

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

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

        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        check[0] = true;

        while (!q.isEmpty()) {
            int num = q.poll();
            check[num] = true;
            for (Integer integer : lists[num]) {
                if (!check[integer]) {
                    q.add(integer);
                    parent[integer] = num + 1;
                }
            }
        }

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

    }

}

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	27396	11727	8664	42.697%