문제

이해

트리의 노드의 개수는 N개이며 입력으로는 N-1개의 간선이 주어진다. 간선은 방향이 없으며 이어진 두 정점이 주어진다.

정점을 입력받아 각 노드의 부모 노드를 출력하면 된다. (1은 항상 루트 노드이다.)

접근

결국 모든 노드의 부모 노드를 알기 위해서는 각 노드를 탐색할 필요가 있다.

1번 노드가 루트인 것을 보아 탐색의 시작점은 1번 노드로 하면 될 것 같다.

탐색의 방법으로는 BFS, DFS 둘 다 상관없을 것 같아 BFS를 이용해 풀이하였다.

간선의 정보는 ArrayList형 배열을 생성하였다. 각 노드에는 부모, 자식 관계와 상관 없이 연결된 노드가 1개 이상 존재하기 때문에 동적 크기인 ArrayList가 필요했고 이는 N개의 노드에 각각 생성해주었다.

BFS의 구체적 과정은 다음과 같다.
1. 1번 노드를 큐에 삽입
2. 반복문 진입 (큐에서 1번 꺼냄)
3. 1번과 연결된 노드를 확인
4. BFS이기 때문에 각 노드의 부모 노드는 1번일 수 밖에 없음
5. 다음으로 탐색하기 위해 연결된 노드를 큐에 삽입

다음 반복에서 연결된 노드들을 확인할 때 연결됐다고 해서 무조건 부모 노드는 아니다. 따라서, 이 때는 이전에 초기화된 부모 노드 값이 있는 지 확인한다. BFS 탐색이기 때문에 부모 노드 정보를 저장할 때 최초로 저장되는 정보가 올바른 정보이기 때문이다.

코드

package java_baekjoon;

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

public class prob11725 {
    static int N;
    static ArrayList<Integer>[] node;
    static int[] parent;
    static Queue<Integer> q;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        node = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            node[i] = new ArrayList<Integer>();
        }
        parent = new int[N + 1];

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int nodeA = Integer.parseInt(st.nextToken());
            int nodeB = Integer.parseInt(st.nextToken());

            node[nodeA].add(nodeB);
            node[nodeB].add(nodeA);
        }

        q = new LinkedList<>();
        q.add(1);
        while (!q.isEmpty()) {
            int now = q.poll();

            for (int i = 0; i < node[now].size(); i++) {
                if (parent[node[now].get(i)] != 0) {
                    continue;
                }
                parent[node[now].get(i)] = now;
                q.add(node[now].get(i));
            }
        }

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

결과