[99클럽 코테 스터디 17일차 TIL + 깊이/너비 우선 탐색(DFS/BFS)] 18126 너구리 구구 파이썬

 

오늘의 학습 키워드

깊이/너비 우선 탐색(DFS/BFS)

공부한 내용 본인의 언어로 정리하기

문제

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

 

코드

n = int(input())
rooms = [[] for i in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    rooms[a].append((b, c))
    rooms[b].append((a, c))
visited = [0] * (n+1)
ans = [0] * (n+1)
q = [1]
while q:
    t = q.pop()
    visited[t] = 1
    for i in range(len(rooms[t])):
        b, dis = rooms[t][i]
        if not visited[b]:
            ans[b] = ans[t] + dis
            q.append(b)

print(max(ans))

 

q를 통해 시작 지점인 1번 방부터 끝 방까지 깊게 파고들며 거리를 계산한 후 각 방에 할당한다. 이후 가장 큰 값을 리턴한다. 

오늘의 회고

dfs/bfs 문제라 어렵지 않게 해결할 수 있었다. bfs를 통해 q에 있는 방들을 차차 하나씩 해결하면 되는 문제여서 간단하게 풀었던 것 같다. 또한 며칠 전에 풀었던 트리 부모 찾기 문제와 비슷하여 쉽게 풀었다.