[백준 코딩테스트] 11725번 트리의 부모 찾기

내 풀이

처음에는 문제를 제대로 못읽고 그래프 탐색만 사용해서 최상위 부모 노드만 출력했는데 알고보니... 바로 이전의 부모 노드를 출력하는 문제여서 조금 헤맸다.
너비우선탐색을 사용해서 바로 상위 노드의 부모 노드를 parent 배열에 저장하도록 하였고 상위 노드가 정해진 애들은 다시 최상위 노드로 갱신되지 않도록 visited 배열을 사용해 방문하지 못하도록 하였다.

이런 이진 탐색 트리를 방문해서 상위 노드를 알아내야 한다.

내 코드

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

public class Main {
    static int n;
    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int[] parent;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        parent = new int[n+1]; // 바로 상위 노드 저장
        arr = new ArrayList[n+1]; // 그래프 연결 (무방향)
        visited = new boolean[n+1]; // 방문 여부 (이미 부모 노드가 정해졌으면 다시 업데이트하지 않음)

        for(int i=1; i<=n; i++){
            arr[i] = new ArrayList<>();
        }
        
        for(int i=1; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a].add(b);
            arr[b].add(a);
        }

        bfs();

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

    static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        visited[1]=true;

        while(!q.isEmpty()){
            int tmp = q.poll();
            for(int next : arr[tmp]){
                if(visited[next]) continue; //이미 방문했다면 방문하지 않음
                visited[next] = true;
                q.add(next);
                parent[next] = tmp;
            }
        }
    }
}