[코테] 백준 11725 트리의 부모 찾기: BFS Java

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

 

문제 이해

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

문제부터 이해를 해야한다.

트리의 루트를 1이라고 했을 때 노드들의 부모 노드의 번호를 출력하는 문제이다.

 

7
1 6
6 3
3 5
4 1
2 4
4 7

위와 같은 예제가 있다.

7은 노드의 갯수, 그 아래는 트리 상 연결된 정점이다.

 

그려보면 아래와 같은 형태임을 알 수 있다.

2번 노드의 부모부터 순서대로 출력하면 답이 나온다.

4
6
1
3
1
4

 

 

전체 코드

queue에 1을 넣고 while문을 돌린다.

queue가 비게 되면 while문이 끝난다.

q에 있는 값을 꺼낸다. 

이는 '부모 노드'의 값이 된다.

처음은 1이다. arr[부모 노드]를 통해 for문을 돌린다.

그렇게 되면, 자식으로 연결된 친구들의 값을 가져올 수 있다. 위 예시로 보면 4와 6이 가져와진다.

parent[자식 노드]에 부모 노드 값을 넣어준다

parent[4] = 1이 된다.

 

순서대로 부모 노드를 출력하기만 하면 돼서 저렇게 부모 노드의 값을 넣어주기만 하면 된다.

핵심은 '순서대로' 출력 인 것 같다. parant[]를 이용해 부모 노드가 뭔지만 알면 된다. 

 

그리고 q에 다시 해당하는 값을 넣어주면서 부모 역할을 할 수 있는 노드를 추가한다.

그렇게 되면 for문이 끝나고, 다시 4가 부모 노드가 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class baekjoon_11725 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 1) 입력 부분
        int n = Integer.parseInt(br.readLine()); // 노드의 갯수
        
        ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
        // 갯수만큼 초기화
        for (int i = 0; i <= n; i++) {
            arr.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 각각 연결해줌
            // ex arr[1] {2} arr[2] {1}
            arr.get(a).add(b);
            arr.get(b).add(a);
        }

        // 2) 구현 부분
        Queue<Integer> q = new LinkedList<>();
        boolean[] visit = new boolean[n + 1]; // 0인덱스 사용 x
        int[] parent = new int[n + 1];

        q.add(1); // 첫번째 노드 추가
        visit[1] = true;

        while (!q.isEmpty()) { // q가 비어있지 않을 때까지
            int v = q.poll();
            for (int next : arr.get(v)) { // arr에서 연결되어있는 node 찾기
                if (!visit[next]) {
                    visit[next] = true;
                    parent[next] = v;
                    q.add(next);
                }
            }
        }


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

}