[BOJ] 백준 11725 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 

---

 

풀이 방법

1. 방향에 대한 조건은 없으므로, 양방향 인접 리스트를 만든다.
2. bfs를 돌리는데 루트인 1번 정점부터 큐에 넣고, 부모를 표시할 배열(parents)을 하나 만든다. 1번 정점은 루트 노드이기 때문에 방문했다는 의미로 만들어둔 배열 1번 인덱스 값을 1로 설정한다.
3. 큐에 들어있는 요소를 꺼내서 그 요소와 연결되어 있는 노드를 찾고 그 정점에 방문하지 않았다면 큐에 넣는다.
4. parents 배열의 인덱스와 찾은 노드의 번호가 같을 경우 큐에서 꺼낸 요소 즉, 부모 노드를 값으로 집어넣는다.

 

문제에 있는 예제 1번으로 설명을 하자면,

루트 노드인 1번 정점과 연결된 6번 4번 노드를 큐에 넣고 배열에 부모 노드 표시를 하고 나서 큐에서 6을 꺼낸 상태

6번과 연결된 1번은 이미 방문이 된 상태고, 3번은 방문되지 않은 상태이니 배열 3번에 부모 노드인 6이라는 값을 넣고 3번을 큐에 넣는다

큐에서 4번을 꺼내서 4번과 연결된 1,2,7번 노드를 봤을 때, 배열에 값이 없는 2번, 7번에 4라는 값을 넣고 2, 7번 정점을 큐에 넣는다.

큐에서 3번을 꺼내서 3번과 연결된 6, 5번 정점을 봤을 때, 배열에 값이 없는 5번에 3이라는 값을 넣고 5번 정점을 큐에 넣는다

모든 정점에 대한 방문이 끝났으므로, 큐가 비는 순간 bfs가 멈추게 된다

 

다음은 Java로 작성한 코드이다.

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

public class B11725 {
    private static final ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    private static int [] parents;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        
        parents = new int[n+1];

        for (int i = 0; i <= n+1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            list.get(a).add(b);
            list.get(b).add(a);
        }

        bfs();

        for (int i = 2; i < parents.length; i++) {
            System.out.println(parents[i]);
        }
    }

    private static void bfs() {
        LinkedList<Integer> q = new LinkedList<>();
        q.offer(1);
        parents[1] = 1;

        while (!q.isEmpty()) {
            int p = q.poll();

            for (int item: list.get(p)) {
                if (parents[item] == 0) {
                    parents[item] = p;
                    q.offer(item);
                }
            }
        }
    }
}