[백준알고리즘] bfs - 11725번 트리의 부모 찾기 문제

첨에는 2부터 N까지 반복문으로 bfs에 하나씩 수를 넣어 찾도록 했었는데

그러려면 하나 찾기 위해 bfs를 매번 돌려야 하므로 시간초과가 난다.

bfs를 한번 수행해서 부모 노드의 값을 담을 배열에 그때그때마다 각각의 부모노드를 담고

bfs가 끝나뒤 이 배열의 값을 차례대로 출력하는 식으로 하면 시간초과가 해결된다.

 

풀이코드

package baekjoonWeek5;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_11725 {     // 백준 트리의 부모찾기 문제
    static int[] visited;
    static ArrayList<Integer>[] tree;
    static Queue<Integer> queue = new LinkedList<>();
    static int[] parentNode;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());    //노드의 개수
        tree = (ArrayList<Integer>[]) new ArrayList[T + 1];    //제네릭 타입
        visited = new int[T + 1];
        parentNode = new int[T + 1];
        for (int i = 0; i < T + 1; i++) {
            tree[i] = new ArrayList<Integer>();     //초기화
        }
        for (int i = 0; i < T-1; i++) {     //트리니까 간선은 노드 개수 -1
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            tree[x].add(y);
            tree[y].add(x);
        }

        visited[1] = 1; //1만 따로 방문체크해줌
        bfs(1);
        for (int i = 2; i <= T; i++) {
            bw.write(Integer.toString(parentNode[i]));
            bw.newLine();
        }

        bw.flush();
        bw.close();
    }

    static void bfs(int nd) throws IOException{
        for (int n : tree[nd]) {
            if (visited[n] == 0) {
                parentNode[n] = nd;
                queue.add(n);
                visited[n] = visited[nd] + 1;
            }
        }
        if (!queue.isEmpty()) {
            bfs(queue.remove());
        }

    }
}