Question

문제 n개의 방으로 이루어진 미로가 있다. 이 미로 내의 임의의 두 방 사이에는 반드시 하나의 경로가 존재하고, 그 경로는 유일하다. 이 방들 중 한 방에는 김주성 조교가 보물을 숨겨 놓았는데, 김진영 조교는 이 보물을 찾길 원한다. 그러기 위해서, 김진영 조교는 김주성 조교에게 특정한 방에 보물이 있는지 물어 본다. 친절한 김주성 조교는 김진영 조교가 옳은 방을 골랐으면 그렇다고 말해 주고, 옳은 방을 고르지 않았다면 그 방에 연결된 복도 중 어느 복도를 따라 가야만 보물을 찾을 수 있는지 말해 준다. 여러분이 할 일은 미로의 구조가 주어졌을 때 김진영 조교가 최악의 경우에 몇 번의 질문을 던져야 하는지 계산해 내는 것이다. 물론, 영리한 김진영 조교는 항상 최선의 질문을 한다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 이후 n-1개의 줄에는 각각 두 개의 숫자가 주어진다. a와 b가 주어졌다면, a번 방과 b번 방 사이에 복도가 있어 왕래할 수 있다는 의미이다. 방의 번호는 1번부터 n번까지 연속해서 붙어 있다. 출력 첫 줄에 김진영 조교가 최선을 다하더라도, 최악의 경우 몇 번의 질문을 던져야 하는지 출력한다. 이 문제를 c++로 풀어줘

Answer 1

IT 지식이 풍부한 고양이 ‘요고’가 답변해 드려요.

김진영 조교가 최악의 경우에 몇 번의 질문을 던져야 하는지 계산하기 위해서는 트리 구조로 미로를 표현하고, 가장 깊이가 깊은 노드를 찾는 것이 핵심이 될 것입니다. 주어진 입력에서 각 방 사이의 관계를 바탕으로 트리를 구성하여 깊이를 계산하면 됩니다. 이후 가장 깊이가 깊은 노드까지의 거리를 측정하여 최악의 경우의 질문 횟수를 구할 수 있습니다. 

c++로 구현할 때는 트리를 구현하고, BFS나 DFS 같은 알고리즘을 활용하여 최단 거리 또는 깊이를 계산할 수 있을 것입니다. 알고리즘을 구현할 때 주의할 점은 문제에서 요구하는 최악의 경우의 질문 횟수를 최적화하여 구현하는 것이 중요합니다. 이러한 과정을 통해 김진영 조교가 최악의 경우에 몇 번의 질문을 던져야 하는지 계산할 수 있을 것입니다.