11725 트리의 부모 찾기 (JAVA)

• 대량의 삽질을 거친 문제...

(삽질1)

• Node 클래스를 만들어 저장하게 되면, 입력의 순서가 뒤바뀌어 들어올 때 부모와 자식 노드가 반대로 트리가 형성 될 가능성이 있다.
• 따라서 인접리스트로 정점과 간선을 저장하여, 방향에 영향을 받지 않는 무방향 그래프의 순회로 문제를 해결하였다.

(삽질2)

• 2 ~ N 까지 각각의 노드의 부모를 찾기위해 BFS를 N-2번 수행시, 시간초과가 발생한다.
• parent 배열을 사용하여, BFS가 한번 수행될때 모든 노드들의 부모값을 저장하고 마지막에는 parent 배열만 출력함으로써 시간을 1/N-2 로 줄일 수 있다.

public class Main{

    static int[] parent;
    static ArrayList<ArrayList<Integer>> graph;

    static int bfs(){
        Queue<Integer> q = new LinkedList<>();
        parent[1] = 1;
        q.offer(1);
        while(!q.isEmpty()){
            int len = q.size();
            for(int i=0; i<len; ++i){
                int v = q.poll();
                for(int nv : graph.get(v)){
                    if(parent[nv] == 0){
                        parent[nv] = v;	// 다음 노드(nv)는 현재 노드(v)에서 출발했음
                        q.offer(nv);	// 즉, 나중에 parent[자식]을 출력하면 부모값을 얻을 수 있음
                    }
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        graph = new ArrayList<ArrayList<Integer>>();
        int n = sc.nextInt();

        for(int i=0; i<=n; ++i)
            graph.add(new ArrayList<Integer>());

        for(int i=0; i<n-1; ++i){
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        parent = new int[n+1];
        bfs();
        for(int i=2; i<=n; ++i) {
            System.out.println(parent[i]);
        }
    }
}