백준 18126. 너구리 구구 (Python)

문제

텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다. 구구의 집으로 들어가는 입구는 한 개이며 입구과 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.

구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는 무더운 여름 햇살을 피해 최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다.

구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.

접근 방법

처음에는 문제를 잘못 이해해서 N번 방 즉, 마지막 번호의 방이 가장 먼 방이라고 착각하고 풀어서 삽질을 했다.

문제의 핵심은 트리로 접근하여 자식이 없는 노드 즉, 리프노드까지의 값 중 최대값을 구하는 것이다.

가령 입력된 데이터를 트리로 나타냈을 때 위와 같이 된다면
리프 노드인 4, 5, 6까지 가는 것 중 최대 거리를 구하면 되는 것이당

코드 구현 시 중요한 건 리프노드인가를 판별하는 것인데, 현재 노드에서 갈 수 있는 노드들을 하나씩 살펴봐서 모두 방문한 경우에 리프노드로 판별해주었다.

위의 경우에서 현재 4번 노드인 경우 2번 노드 방문체크를 하여 이미 방문한 곳이면 리프노드인 것이다.
반대로 현재 2번 노드인 경우 1번은 방문했고 4번은 방문하지 않았다면 리프노드가 아닌 것이다.
( + 나는 재귀로 작성했는데 스택으로 작성하면 더 빠르게 작동한다.)

코드

import sys
sys.setrecursionlimit(5002) # 재귀 max depth

def dfs(s, far):
    global ans
    # flag 변수를 통해 리프노드인지를 판별
    flag = 0
    for j in lst[s]:
    	# 현재 노드에서 다른 노드를 모두 방문했다면
        if chk[j[0]] == 0:
            flag = 1
    # 리프 노드인 경우 max값 갱신
    if flag == 0:
        if far > ans:
            ans = far
        return
    # 리프가 아니면 계속 방문 탐색
    for i in lst[s]:
        if chk[i[0]] == 0:
            chk[i[0]] = 1
            dfs(i[0], far+i[1])
            chk[i[0]] = 0

N = int(input())
room_info = sorted([list(map(int,input().split())) for _ in range(N-1)])
lst = [[] for _ in range(N+1)]
for room in room_info: # 양방향
    lst[room[0]].append([room[1],room[2]])
    lst[room[1]].append([room[0],room[2]])

chk = [0] * (N+1)
ans = 0
chk[1] = 1 # 1번방은 미리 방문 체크
dfs(1,0)
print(ans)