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

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

풀이

사용한 알고리즘 : BFS, 트리구조

 

풀이전략

1. 주이진 입력을 BFS를 사용하여 트리로 만든다.

2. BFS로 탐색 중, 특정 노드의 부모 노드를 저장해둔다.

3. 저장해뒀던 부모 노드들을 출력한다.

 

제출코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    static boolean visited[];
    static int parent[];

    static void bfs(int x){
        Queue<Integer> q = new LinkedList<>();
        q.offer(x);
        while(!q.isEmpty()){
            int now=q.poll();
            for(int a:graph.get(now)){
                if(!visited[a]){
                    visited[a]=true;
                    parent[a]=now;
                    q.offer(a);
                }
            }
        }
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        for(int i=0;i<N+1;++i){
            graph.add(new ArrayList<Integer>());
        }
        visited=new boolean[N+1];
        parent=new int[N+1];

        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());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

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