[백준] 11725 - 트리의 부모 찾기 (JAVA)

[백준] 트리의 부모 찾기

처음엔 트리!!??? 라고 해서 괜히 겁먹었지만 문제를 천천히 읽어보니 결국은 dfs, bfs 문제였다.
dfs, bfs 둘 다 비슷하게 메모리와 시간이 소요된다.

간단한 bfs, dsf 문제이기 때문에 다른 풀이들과 전반적인 코드는 비슷하다.
다만 visited 배열과 부모 노드를 담는 배열을 따로 따로 선언할 필요가 없어 보이길래 그냥 visited 배열을 int 배열로 만들어서 값이 0인 경우에는 방문하지 않은 노드로 체크하고, 해당 인덱스의 배열 값에 부모 노드의 숫자를 넣도록 코드를 작성했다.

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

// 11725 - 트리의 부모 찾기
public class Main {
    static List<List<Integer>> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            list.get(n1).add(n2);
            list.get(n2).add(n1);
        }
        int[] visited = new int[list.size()];
        visited[1] = 1;
        bfs(1, visited);
//        dfs(1, visited);

        for (int i = 2; i < visited.length; i++) {
            bw.write(visited[i]+"\n");
        }
        bw.flush();
        bw.close();
    }

    static void dfs(int p, int[] visited) {
        for (int node : list.get(p)) {
            if(visited[node] == 0){
                visited[node] = p;
                dfs(node, visited);
            }
        }
    }

    static void bfs(int root, int[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            for (int node : list.get(poll)) {
                if(visited[node] == 0){
                    visited[node] = poll;
                    queue.add(node);
                }
            }
        }
    }
}