[백준] 너구리 구구

문제

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

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

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

 

입력

첫째 줄에 정수 N(1 ≤ N ≤ 5,000)이 주어진다.

다음 N-1개의 줄에 구구의 집의 모든 길의 정보가 정수 A, B, C(1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000)로 주어진다.

A번 방과 B번 방 사이를 양방향으로 연결하는 길의 길이가 C임을 의미한다.

출력

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

예제 입력 1 

4
1 2 3
2 3 2
2 4 4

예제 출력 1 

7

 

나의 문제 풀이 전략

BFS를 이용하여 문제를 풀었다. 이차원 리스트로 그래프를 만들고 각 연결되어 있는 방들간의 거리 값을 넣어주었다. 

 

나의 코드

from collections import deque

N = int(input())
visited = [False for i in range(N+1)]
graph = [[0]*(N+1) for _ in range(N+1)]

distance = 0

def BFS(s):
    global distance
    q = deque()
    visited[s] = True
    q.append((s,0)) # 현재의 방번호와 시작점으로부터의 거리 값 큐에 삽입

    while(q):
        v,c = q.pop()
        visited[v] = True
        distance = max(distance, c)
        for i in range(1, N+1):
            if visited[i]: continue
            if graph[v][i] != 0:
                q.append((i,c+graph[v][i]))



for i in range(N-1):
    A, B, C = map(int, input().split())
    graph[A][B] = C
    graph[B][A] = C

BFS(1) # 처음에 1을 넣음으로써 초기세팅

print("Distance: ", distance)