[파이썬/python] 백준 18126 - 너구리 구구

문제

https://www.acmicpc.net/problem/18126

---

문제 설명

1. 너구리 구구는 총 N개의 방을 가지고 있다.
2. 입구를 포함한 모든 방은 1부터 N까지 번호를 가지고 있다.
   1. 이 때 입구는 1번이다.
3. 구구는 입구에서 가장 먼 방에 아이스크림을 숨기려고 한다.
4. 구구가 집 입구에서 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구해라. 

 

---

BFS 혹은 DFS를 통해 가장 먼 방까지의 거리를 구하는 문제다.

이 때 문제에서 "모든 길은 서로 오고 갈 수 있다."라는 말이 있기 때문에 양방향 그래프로 구현했다.

풀이

1. 입력받은 간선 정보를 통해 양방향 그래프를 생성한다.
2. 1번 노드가 입구 즉 루트 노드이므로 1번 노드부터 탐색을 진행한다.
3. 순차적으로 방을 이동하면서 최대 거리를 갱신한다.

---

코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())


graph = [[] for _ in range(n+1)]

queue = deque([])
visited = [0 for _ in range(n+1)]

def bfs():
    max_dist = -1
    while queue:
        v1, dist= queue.popleft()
        max_dist = max(dist, max_dist)
        for v2,cost in graph[v1]:
            if not visited[v2]:
                visited[v2] = 1
                queue.append((v2, dist+cost))
    return max_dist


for i in range(n-1):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))
queue.append((1,0))
visited[1] = 1
print(bfs())

---

시간복잡도

• 인접 그래프 방식의 BFS 시간복잡도는 $O(V+E)$이다.
  • V : 정점의 개수
  • E : 간선의 개수
• 노드(정점)의 최대 개수는 $5*10^3$, 간선의 최대 개수는 $5*10^3 - 1$
• 따라서 최악의 경우 시간복잡도는 약 $O(10^4 -1)$이다.