| 시간 제한 | 메모리 제한 |
| 1초 | 128MB |
문제
(원문이 영어라 gpt에게 번역 하청 맡김)
Bessie는 아름다운 봄날 외양간 문을 열고, "싱그러운 봄 풀을 먹기 위해 목초지까지 가는 길을 천천히 즐기고 싶어"라고 생각합니다. Bessie는 외양간을 떠나면, 길을 따라가다가 갈림길에 도달하여 두 가지 선택 중 하나를 선택하고, 선택한 길을 따라가서 다시 다른 갈림길을 만나게 되며, 이를 반복하여 결국 푸르른 목초지로 가는 길을 찾게 될 것임을 알고 있습니다.
Bessie는 아침 식사로 가는 길에 최대한 많은 소의 길을 지나가도록 하는 경로를 선택하기로 합니다. 주어진 경로 설명을 바탕으로, 외양간을 떠난 직후부터 다양한 경로를 선택한다고 가정할 때, Bessie가 지나가는 소의 길의 수를 구하세요.
농장은 P개의 목초지(1 ≤ P ≤ 1,000)로 구성되어 있으며, 각 목초지는 P−1개의 선택 노드(범위 1..P−1)와 길로 연결되어 있습니다. 외양간(노드 1)에서 출발하여 각 선택 노드나 목초지에 도달할 수 있는 경로 집합이 유일하게 존재합니다.
아래 예시는 경로 집합(선), 목초지('%'), 선택 경로('#')로 구성되어 있으며, 목초지 오른쪽의 경로를 나타냅니다: (생략)
입력
첫 번째 줄: 단일 정수 P
2번 줄부터 P번 줄까지: 각 줄에는 선택 노드에 대한 세 개의 정수 Cn, D1, D2가 주어집니다. 여기서:
Cn : 노드 번호 (1 ≤ Cn ≤ P−1)
D1 : 첫 번째 선택 방향 (0 ≤ D1 ≤ P−1)
D2 : 두 번째 선택 방향 (0 ≤ D2 ≤ P−1)
만약 D1 또는 D2가 0이면, 그 방향은 목초지로 향하는 길을 나타냅니다.
출력
첫 번째 줄: Bessie가 가장 먼 목초지로 가는 길에 지나갈 수 있는 최대 경로 수를 나타내는 단일 정수.
풀이
문제 설명이 굉장히 난해해서 이해하는데 애먹은 문제. 우선 P개의 목초지가 있고 P-1개의 선택 노드와 길로 연결되어 있다, 외양간에서 출발해 각 선택 노드나 목초지에 도착하는 경로는 유일하게 존재한다는 것으로 보아 목초지로 이어지는 경로들은 순환이 없는 트리 형태임을 알 수 있다. 그리고 입력이 반드시 Cn, D1, D2로 고정되어있다. 모든 노드는 최대 두 개의 자식 노드와 이어져 있는 대충 이진 트리의 형태라고 봐도 되겠다. 가장 멀리 있는 목초지를 구하란다. 0으로 넘어가는 가장 오랜 탐색 횟수를 출력하면 되겠다.
같은 깊이의 탐색을 모두 수행하고 다음 깊이로 넘어가는 너비우선탐색을 실시하면, 가장 마지막 탐색 깊이가 반드시 정답이 된다. (물론 깊이우선탐색을 해서 최대 탐색깊이를 출력해도 된다.)
정답 코드
import sys
from collections import deque
input = sys.stdin.readline
def solution():
P = int(input())
tree = [[] for _ in range(P)]
for _ in range(P - 1):
C, D1, D2 = map(int, input().split())
tree[C] += [D1, D2]
bfs = deque([(1,1)])
far = 0
while bfs:
node, depth = bfs.popleft()
for next in tree[node]:
if next:
bfs.append((next, depth + 1))
else:
far = depth
print(far)
solution()
