[Python] 백준/BOJ 18126번: 너구리 구구 (Silver 2)

💻 Problem

문제 보러 가기

 

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

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

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

 

💡 Approach

처음에 이 문제를 봤을 때 간선에 가중치가 있으니 다익스트라 문제 아닌가? 싶었다.

하지만 다익스트라는 최단 거리를 찾는 알고리즘이고 이 문제는 가장 먼 노드를 찾는 문제이므로 dfs 또는 bfs로 풀어야 한다.

 

먼저 길의 정보를 저장하는 그래프를 만든다.

예제 입력 1 그래프

예제 입력 1을 바탕으로 그래프를 만들면 위와 같은 그래프가 만들어진다.

튜플 안의 값은 순서대로 연결된 방 번호, 길의 길이이다.

 

그럼 이제 그래프가 준비되었으니 가장 먼 방을 찾으러 가자~

 

나는 dfs로 풀었다.

1번 방부터 탐색을 시작해서 현재 위치한 방을 방문 처리하고 현재 위치한 방과 연결된 방들을 살펴보았다.

아직 방문하지 않은 방이면 여태까지 이동한 거리에 다음 방으로 가는 길의 길이를 더해 다음 방으로 이동하도록 했다.

dfs 재귀 순서

탐색 순서를 그림으로 표현하면 위와 같다.

visited는 편의상 그림에 index 0은 표기하지 않았다.

 

✏️ Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 4)

def find_room(cur, dst):
    global ans
    # 현재 위치한 방 방문 처리
    visited[cur] = True
    # 현재 위치한 방이 시작점에서 더 먼 방이면 거리 갱신
    ans = max(ans, dst)

    # 현재 위치한 방과 연결된 방들 탐색
    for node, length in graph[cur]:
        # 아직 방문하지 않은 방이면 여태까지 이동한 거리에 다음 방으로 가는 길의 길이를 더해 다음 방으로 이동
        if not visited[node]:
            find_room(node, dst + length)

n = int(input()) # 방 개수
graph = [[] for _ in range(n + 1)] # 방 사이의 길 정보
visited = [False] * (n + 1)
ans = 0 # 가장 먼 방까지의 이동 거리

for _ in range(n - 1):
    n1, n2, length = map(int, input().split())
    # n1 <-> n2 양방향 길
    graph[n1].append((n2, length))
    graph[n2].append((n1, length))

# 가장 먼 방 찾기
find_room(1, 0)
print(ans)

 

⚠️ 런타임 에러 (RecursionError)

이 코드를 처음 제출했을 때는 런타임 에러 (RecursionError)가 떴다.

Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어지면 이 에러가 뜬다고 한다.

처음에는 내가 코드를 잘못 짜서 재귀가 너무 깊어져 문제가 생긴 줄 알았다.

그러나 백준 문서를 확인해 보니 sys.setrecursionlimit()을 활용하면 최대 재귀 깊이를 변경할 수 있다고 한다.

 

넉넉하게 설정해도 되지만, 한 번 테스트를 해보기 위해 타이트하게 계산해 보겠다.

이 문제에서는 N의 최댓값이 5,000이므로 트리의 깊이 또한 최대 5,000까지 갈 수 있다.

5,000은 5 x 10 ^ 3이므로 최대 재귀 깊이를 10 ^ 4로 설정하면 통과할 것이다.

 

확인해 보기 위해 10 ^ 3으로 설정해서 제출해 보고 10 ^ 4으로 설정해서 제출해 봤다.

전자로 했을 때는 RecursionError가 뜨고 후자로 했을 때는 통과하는 것을 확인할 수 있다.

 

만약 최대 재귀 깊이를 너무 크게 설정했을 때는 OverflowError가 발생했다.

 

앞으로 dfs로 문제를 풀 때는 이 점을 확인해야겠다.

 

⏱️ 시간복잡도

• O(n)

노드(방)의 개수와 간선(방 사이의 길)의 개수를 더하면 n + (n - 1)이다.

즉, 2n - 1이므로 n의 최댓값인 5,000을 대입하면 10,000 - 1 = 10 ^ 4 - 1이다.