BOJ_1868_보물찾기 (Java)

[Ruby V] 보물찾기 - 1868

문제 링크

성능 요약

메모리: 34856 KB, 시간: 300 ms

분류

다이나믹 프로그래밍, 트리에서의 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 그리디 알고리즘, 트리

제출 일자

2025년 1월 23일 01:37:28

문제 설명

n개의 방으로 이루어진 미로가 있다. 이 미로 내의 임의의 두 방 사이에는 반드시 하나의 경로가 존재하고, 그 경로는 유일하다.

이 방들 중 한 방에는 김주성 조교가 보물을 숨겨 놓았는데, 김진영 조교는 이 보물을 찾길 원한다. 그러기 위해서, 김진영 조교는 김주성 조교에게 특정한 방에 보물이 있는지 물어 본다. 친절한 김주성 조교는 김진영 조교가 옳은 방을 골랐으면 그렇다고 말해 주고, 옳은 방을 고르지 않았다면 그 방에 연결된 복도 중 어느 복도를 따라 가야만 보물을 찾을 수 있는지 말해 준다.

여러분이 할 일은 미로의 구조가 주어졌을 때 김진영 조교가 최악의 경우에 몇 번의 질문을 던져야 하는지 계산해 내는 것이다. 물론, 영리한 김진영 조교는 항상 최선의 질문을 한다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 이후 n-1개의 줄에는 각각 두 개의 숫자가 주어진다. a와 b가 주어졌다면, a번 방과 b번 방 사이에 복도가 있어 왕래할 수 있다는 의미이다. 방의 번호는 1번부터 n번까지 연속해서 붙어 있다.

출력

첫 줄에 김진영 조교가 최선을 다하더라도, 최악의 경우 몇 번의 질문을 던져야 하는지 출력한다.

문제 풀이

접근

• 비트마스크를 사용하여 각 서브트리의 “깊이 정보”를 관리
• DFS를 통해 트리를 순회하며 각 노드에서 필요한 질문 횟수를 계산
• 서브트리들이 겹치는 경우를 처리하여 최적의 질문 횟수를 도출

비트마스크 활용

// 비트마스크의 의미
0001 (1) = 깊이 0 = 바로 인접한 방 확인
0010 (2) = 깊이 1 = 2번의 질문 필요
0100 (4) = 깊이 2 = 3번의 질문 필요

예시

예시와 설명 다음과 같은 트리 구조를 생각해봅시다:

    1
   / \
  2   3
 /     \
4       5

1. 노드 4와 5는 리프 노드로, 비트마스크 0001 을 반환
2. 노드 2와 3은 각각 하나의 자식을 가지므로, 비트마스크를 조정
3. 루트 노드 1에서는 두 서브트리의 정보를 합치고 필요한 질문 횟수 계산

시간 복잡도

• DFS를 사용하여 트리를 한 번 순회: O(N)
• 각 노드에서의 비트 연산: O(1)
• 전체 시간 복잡도: O(N)

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, a, b, res;
    static ArrayList<Integer>[] tree;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1868_보물찾기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        N = Integer.parseInt(br.readLine());
        tree = new ArrayList[N+1];
        for(int i = 1; i < N+1; i++){
            tree[i] = new ArrayList<>();
        }

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

            tree[a].add(b);
            tree[b].add(a);
        }

        res = dfs(1, 0);

        bw.write(String.valueOf(31 - Integer.numberOfLeadingZeros(res)));
        bw.flush();
        bw.close();
        br.close();
    }

    private int dfs(int curr, int parent){
        int currBitMask = 0; // 비트마스크를 사용하여 서브트리의 상태를 관리 (깊이)
        /*
            이진수: 0001 = 깊이 0 = 바로 옆 방을 확인하면 됨
            이진수: 0010 = 깊이 1 = 2번의 질문이 필요함
            이진수: 0100 = 깊이 2 = 3번의 질문이 필요함
         */
        int maxHeight = 0;

        /*
            각 노드에서:
              - 자식 노드들의 결과를 비트마스크로 합침
              - 겹치는 부분이 있으면 그 중 가장 높은 비트 위치를 찾음
              - 현재 노드의 비트마스크를 적절히 조정
         */

        // 현재 노드의 모든 자식 노드들 순회
        for(int child : tree[curr]){
            if(child == parent) continue;

            // 자식서브트리 결과
            int childBitMask = dfs(child, curr);

            // 현재 비트마스크와 자식 결과 사이에 겹치는 서브트리 있으면
            if((childBitMask & currBitMask) != 0){
                // 겹치는 비트 중 가장 높은 위치 찾기, 즉 더 깊은 깊이가 필요함
                maxHeight = Math.max(maxHeight, 31- Integer.numberOfLeadingZeros(childBitMask & currBitMask));
            }

            // 현재 비트마스크에 자식결과 합침
            currBitMask |= childBitMask;
        }

        // 현재 노드의 최종 비트마스크 계산
        currBitMask += 1 << maxHeight; // 갈래가 2개면 (4, 5), 한번 더 진행해야한다는 것이므로 깊이 하나 증가한다는 의미

        // maxHeight가 0이 아니면 비트마스크 조정 (겹치는 깊이 정보를 제거하기 위해)
        /*
            1
           / \
          2   3
         /     \
        4       5
        이런 트리가 있을 때 조정하지 않은 경우:
            - 2번 노드에서: 0001 (깊이 0)
            - 3번 노드에서: 0001 (깊이 0)
            - 1번 노드에서 이 값들을 합치면: 0011
        문제점: 이렇게 되면 "같은 깊이에서 두 개의 선택지가 있다"고 잘못 해석됨
         */
        if(maxHeight > 0){
            currBitMask >>= maxHeight;
            currBitMask <<= maxHeight;
        }
        return currBitMask;
    }
}