[파이썬] 백준 1595 : 북쪽나라의 도로 (골드4)

[파이썬] 백준 1595 : 북쪽나라의 도로 (골드4)

• https://www.acmicpc.net/problem/1595
  

---

풀이

방향성 생각

• BFS를 통해서 한 점에서 가장 끝 점으로 간 후 BFS를 돌려준다.

• 트리의 지름을 구하는 문제와 동일한 발상

---

전체코드

from collections import deque, defaultdict as dd
import sys
input = lambda: sys.stdin.readline().rstrip()

graphs = dd(list)
while True:
    try:
        a,b,c = map(int,input().split())
        graphs[a].append((b,c))
        graphs[b].append((a,c))
    except:
        break

def bfs(x):

    visit = dd(int)
    visit[x] = 0
    q = deque([(x,0)])

    while q:
        x,c = q.popleft()
        for nx,cost in graphs[x]:
            nc = c + cost
            if nx not in visit:
                visit[nx] = nc
                q.append((nx,nc))
    return visit

if not graphs:
    print(0)
else:
    a,c = max(bfs(b).items(),key = lambda x:x[1])
    print(max(bfs(a).values()))

코멘트

• 예전에 10트해서 못풀었었는데, strip 대신 stip써서 통과 안됐음...