11725번

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

11725번: 트리의 부모 찾기

이번에 풀은 문제는 트리구조 관련 문제라고 생각하고 풀었는데, 알고보면 그냥 BFS문제이다.

간단하게 생각하면 된다. 시작 노드를 1로 하고 인접 노드들의 위치에 부모 노드인 1을 집어 넣고, 그 다음 인접 노드에는 1의 자식 노드들을 집어 넣고 하면 된다.

말로하면 이게 무슨 말인가 싶을 수도 있다. 그래서 예제를 따왔다.

예제에서 주어진 입력을 BFS에서 사용하는 간선 추가를 위한 입력으로 생각하고, 시작 노드를 1로 해서 BFS로 탐색을 진행하면,

1과 연결된 노드는 2,3이고 2와 연결된 노드는 4, 3과 연결된 노드는 5,6 ... 이런 식으로 되어 있는데, 그러면 2와 3의 부모 노드는 1이고 4의 부모 노드는 2이다. 5,6의 부모 노드는 3이다. 그러면 BFS로 탐색을 진행한다고 하면 부모노드가 무엇인지 저장할 배열의 1에는 무엇을 넣던 상관없다. 그리고 2와 3에는 부모 노드인 1을 넣는다. 그리고 2의 인접 노드인 4에는 2를 넣고, 3의 인접노드 5,6에는 3을 넣는다.

이를 계속 진행하게 된다.

이해를 위해 아래의 그림을 준비했다.

즉, BFS로 탐색을 진행하면서 인접 노드들의 index에는 큐에서 가져온 노드를 부모 노드로 넣으면 된다.

그래서 정답코드는 아래와 같다.

package backjoon.b11725;

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

public class b11725 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Graph g = new Graph(N);
        for(int i=0; i<N-1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            g.addEdge(u,v);
        }
        g.bfs();
        StringBuilder sb = new StringBuilder();
        for(int i=2; i<=N; i++){
            sb.append(g.parent[i]).append("\n");
        }

        System.out.println(sb);
    }
}
class Graph{
    int[] parent;
    boolean[] visit;
    Queue<Integer> queue;
    int N;

    LinkedList<Integer>[] adj;
    public Graph(int n){
        parent=new int[n+1];
        visit = new boolean[n+1];
        N=n;
        queue = new LinkedList<>();
        adj = new LinkedList[n+1];
        for(int i=0; i<=n; i++){
            adj[i]=new LinkedList<>();
        }
    }

    public void addEdge(int u, int v){
        adj[u].add(v);
        adj[v].add(u);
    }

    public void bfs(){
        queue.add(1);
        visit[1]=true;
        parent[1]=1;
        while (!queue.isEmpty()){
            int tmp = queue.poll();
            for(int i : adj[tmp]){
                if(!visit[i]){
                    queue.add(i);
                    visit[i]=true;
                    parent[i]=tmp;
                }
            }
        }
    }
}