(11752) 트리의 부모 찾기

문제

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

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

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

---

문제 풀이

주어진 트리에서 각노드의 부모를 구하는 문제이다. BFS(Binary  Find Search) 알고리즘을 활용하여 해당 문제를 해결 할 수 있었다. 

 

노드의 개수 n과 트리의 연결 정보를 입력으로 받아 ArrayList 배열을 이용하여 인접 리스트를 구성한다. 

static ArrayList<Integer>[] tree;

인접 리스트로 구성된 값들은 아래 표와 같다.

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

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

ArrayList<Integer>[] 에 입력된 값

 

부모 노드의 정보를 담을 수 있는 parent 배열을 선언 및 초기화를 해준다. 

static int[] parent;

BFS 탐색을 시작하기 위해 방문 여부를 체크할 visited 배열과 Queue를 선언한다. 

boolean[] visited = new boolean[n + 1];
Queue<Integer> queue = new LinkedList<>();

시작노드 1을 방문 체크하고 큐에 추가해준다. 

queue.offer(1);
visited[1] = true;

큐가 빈 값이 될 때 까지 반복문을 수행하면서 현재 노드에서 갈 수 있는 자식 노드들을 순회한다. 

자식 노드를 아직 방문하지 않았다면, visted 배열을 true로 설정하고 parent 배열에 현재 노드 정보를 저장한 뒤, 큐 에 자식 노드를 추가한다. 

 

BFS 탐색이 끝나면 parent 배열을 순회하여 노드 2부터 각 노드의 부모 노드 정보를 출력한다. 

---

나의 답안

import java.util.*;

public class Main {
    static int n;
    static ArrayList<Integer>[] tree;
    static int[] parent;

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

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

        parent = new int[n + 1];

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

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

        bfs();

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

    }

    private static void bfs() {
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(1);
        visited[1] = true;

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

            for (int child : tree[cur]){
                if (!visited[child]) {
                    queue.offer(child);
                    parent[child] = cur;
                    visited[child] = true;
                }
            }

        }

    }
}