[BOJ_11725] 트리의 부모 찾기

설명

---

방문 여부를 체크하는 일반적인 그래프의 탐색을 구현하였다. 하지만, visited 처리 중 처음 스타트 지점의 처리를 잘 못해서 result가 이미 셋팅된 경우에는 다시 셋팅을 반복하지 않도록 방문 여부를 체크하지 못한 스타트 지점의 처리를 해주었는데 조금 아쉬운 코드이다.

 

 

코드

---

package tree;

import java.util.*;

public class BOJ_11725 {

    static int result[];
    static boolean visited[];
    static List<Integer>[] list;
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        list = new ArrayList[N + 1];
        for (int i = 0; i < list.length; i++){
            list[i] = new ArrayList<Integer>();
        }
        result = new int[N+1];
        for (int i = 0; i < N-1; i++){
            int from = sc.nextInt();
            int to = sc.nextInt();
            list[from].add(to);
            list[to].add(from);
        }
        visited = new boolean[N+1];
        bfs(1);
        for (int i = 2; i < result.length; i++){
            System.out.println(result[i]);
        }
    }

    private static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>(list[start]);
        for (int i = 0; i < list[start].size(); i++){
            result[list[start].get(i)] = start;
        }
        while(!q.isEmpty()){
            int parents = q.poll();
            for (int i = 0; i < list[parents].size(); i++){
                if(!visited[list[parents].get(i)]) {
                    visited[list[parents].get(i)] = true;
                    if(result[list[parents].get(i)] == 0) {
                        result[list[parents].get(i)] = parents;
                    }
                    q.add(list[parents].get(i));
                }
            }
        }
    }
}

11725번: 트리의 부모 찾기