[백준/Java] 11725번 : 트리의 부모 찾기

🌵 문제 분석

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

숫자 N과 N-1개의 인접 노드 정보가 주어졌을 때

1을 루트로 할 경우 2~N까지의 각 노드의 부모 노드가 누구인지 출력하는 문제이다.

🌵 구현 아이디어

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

1️⃣ 먼저 인접 노드를 저장한다.

이중 연결리스트를 생성해서 인접 노드 정보를 저장한다.

1 6이 입력값으로 들어오면 list.add(1)=6, list.add(6)=1 이런 식으로 양방향으로 참조할 수 있게 저장한다.

(양방향으로 저장해야 루트부터 탐색 시 모든 노드를 방문할 수 있음)

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

2️⃣ 인접 노드 리스트를 참고해서 루트(1)부터 탐색 시작, 부모 노드 구하기

이해를 위해 인접 리스트를 시각화하면 위와 같다.

부모 노드가 누군지 저장할 ans배열을 하나 만들고 ans에 탐색 결과를 순차적으로 저장한다.

 

1과 인접한 곳에 6, 4가 있으므로 노드 6, 4의 부모 노드는 루트인 1이 된다. ans[6] = ans[4] = 1 

그리고 그 후의 탐색은 인접 리스트의 6, 4로 각각 분기된다.

6과 인접한 곳에 3이 있으므로 노드 3의 부모 노드는 6이다. ans[3] = 6

4와 인접한 곳에 2, 7이 있으므로 노드 2, 7의 부모 노드는 4이다. ans[2]=ans[7]=4

...

 

부모 노드가 누군지 찾을 때마다 check배열에 부모 노드를 찾았다고 체크해주면 중복 연산을 줄일 수 있다.

이렇게 모든 노드의 부모를 다 찾으면 ans에 저장된 값을 차례로 출력한다.

🌵 공간 복잡도/시간 복잡도

처음엔 N*N 인접 행렬을 쓰려고 했는데

공간 복잡도가 O(N*N) * 4byte = 40,000,000,000 byte > 256,000,000byte라서

인접 리스트를 쓰기로 했다.

 

인접 리스트를 저장하는 시간 복잡도 : O(N-1)

인접 리스트를 루트부터 순회하며 부모 노드를 찾는 시간 복잡도 : O(2N)

 

전체 시간 복잡도는 O(2N)이고 N은 최대 100,000이므로 1초 안에 연산 가능하다. 

🌵 알고리즘

그래프 탐색

🌵 코드 설계

1. 입력 받기
   1. N에 인접 노드의 수 저장
   2. List<Integer> list에 인접 노드를 양방향으로 저장
      1. list.add(i) = k
      2. list.add(k) = i
2. 인접 리스트를 참고해서 각 노드의 부모 노드가 누군지 저장
   1. 부모 노드 구하기 전 처리해줄 것
      1. 부모 노드가 누군지 저장할 배열 int[N+1] ans 선언
      2. 부모 노드를 이미 구했는지 표시할 배열 boolean[N+1] check 선언
      3. 1은 루트 노드 이므로 ans[1] = 0, check[1] = true
   2. 부모 노드 구하기 
      1. 큐에 1을 넣고 시작
      2. 큐가 빌 때까지 아래 과정 반복
      3. 큐에서 하나를 꺼내어 p에 저장, p의 자식 노드를 children에 저장
         List<Integer> children = list.get(p)
      4. children의 부모를 p로 저장하기
         for: 0<i<children.size()만큼 반복하면서
         if(!check[i]) ans[children.get(i)] = p
         check[i] = true
         q.add(children.get(i))
3. 부모 노드 출력하기

🌵 정답 코드

import java.util.*;

public class FindParent {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 노드 개수
        List<List<Integer>> list = new ArrayList<>();

        // 인접 리스트 초기화
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }

        // 간선 입력 받기 (양방향)
        for (int i = 0; i < N - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            list.get(a).add(b);
            list.get(b).add(a);
        }

        // 부모 노드 저장할 배열 & 방문 체크 배열
        int[] ans = new int[N + 1];
        boolean[] check = new boolean[N + 1];

        // BFS로 부모 노드 찾기
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        check[1] = true;
        ans[1] = 0; // 루트 노드는 부모가 없음

        while (!queue.isEmpty()) {
            int p = queue.poll(); // 부모 노드

            // 현재 노드(p)의 자식 리스트 가져오기
            List<Integer> children = list.get(p);

            for (int child : children) {
                if (!check[child]) { // 아직 방문하지 않은 노드만 처리
                    ans[child] = p; // 부모 저장
                    check[child] = true;
                    queue.add(child);
                }
            }
        }

        // 부모 노드 출력 (2번 노드부터 출력)
        for (int i = 2; i <= N; i++) {
            System.out.println(ans[i]);
        }

        sc.close();
    }
}