[백준] 11725번 : 트리의 부모 찾기

문제

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

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

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

문제해결방법

정점의 연결들을 표현해주고 1번 노드부터 BFS를 돌면서 부모를 표시해준다.

POINT

처음에 노드의 개수 N (2 ≤ N ≤ 100,000) 를 제대로 안읽고 이차 배열로 풀다가 메모리 초과가 떴다.

다음은 연결 리스트로 노드들의 연결을 나타내 주려고 했는데 LinkedList로 했다가 시간 초과가 났다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main11725_트리의부모찾기 {
 
    public static int[] v;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        v = new int[n+1];
        List<List<Integer>> map = new ArrayList<>();
        for(int i=0; i<=n; i++) map.add(new ArrayList<>());
        for(int i=0; i<n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map.get(a).add(b);
            map.get(b).add(a);
        }
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        v[1] = -1;
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int child : map.get(cur)) {
                if(v[child]==0) {
                    q.add(child);
                    v[child]=cur;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=2; i<=n; i++) sb.append(v[i]+"\n");
        System.out.println(sb.toString());
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.