문제 설명

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

생각

구하는 것은 각 노드의 부모노드(의 번호)이다.
노드 번호는 1 부터 N까지.
1이 루트라고 정해져있다.

각 노드의 인접 노드 리스트를 만들어 놓고 bfs로 순회하며 parents 배열에 넣어주면 된다.

---

풀이

package _03._0327.b11725;

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));
        int N = Integer.parseInt(br.readLine());
        int[] parents = new int[N+1];
        List<Integer>[] adj = new List[N+1];
        for (int i = 0; i < adj.length; i++) adj[i] = new ArrayList<>();

        for(int i = 0; i < N - 1; i++) {
            int[] edge = getEdge(br.readLine());
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        bfs(adj, parents);

        StringBuilder sb = new StringBuilder();
        for(int i = 2; i < parents.length; i++) {
            sb.append(parents[i]).append(System.lineSeparator());
        }
        System.out.println(sb);
    }

    private static void bfs(List<Integer>[] adjList, int[] parents) {
        boolean[] visited = new boolean[adjList.length];
        Deque<Integer> q = new LinkedList<>();
        q.add(1);
        while(!q.isEmpty()) {
            int curr = q.poll();
            for (int adj : adjList[curr]) {
                if(!visited[adj]){
                    parents[adj] = curr;
                    q.offer(adj);
                }
            }
            visited[curr] = true;
        }
    }

    private static int[] getEdge(String line) {
        int idx = 0;
        for(int i = 0; i < line.length(); i++) {
            if(line.charAt(i) == ' ') {
                idx = i;
                break;
            }
        }
        return new int[]{
                Integer.parseInt(line.substring(0, idx)),
                Integer.parseInt(line.substring(idx+1))
        };
    }
}

입력 시간 좀 줄이고자 getEdge라는 함수를 만들어 활용했다.
split 보다 빠를 것이다.
StringTokenizer 보다 가벼울 것이다.

adj 리스트 배열과 parents 노드 배열의 인덱스는 노드 번호를 의미한다.

너비 우선 탐색. 루트 노드는 1이라고 정해져 있으니 큐에 1을 넣어 놓는다.
큐에서 하나 꺼내면 그 노드의 인접 노드들을 큐에 넣는다. 이 때, 인접 노드가 이미 순회한 노드라면 무시한다. parents 배열에도 넣어준다.
큐가 빌 때까지 반복한다.

---

마무리

오랜만의 비선형 자료구조 문제이다.
너무 오랜만이라 좀 헤맸다. 다음의 이유로 시간을 좀 써버렸다.

1. 이진 트리라고 가정해버렸다.
2. bfs보다 빠른 풀이가 있을 줄 알았다.

그래도 bfs 문제라는 걸 인지한 후로는 바로 풀렸다.

문제 보면 빠르게 방향을 잡을 수 있도록 비선형 문제를 좀 더 많이 풀어야겠다.