99클럽 코테스터디 17일차 TIL - 백준 18126

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

이 문제는 DFS를 활용하여 푸는 문제다. 문제에서 다음과 같은 근거를 찾았다

- 입구는 1번이며, 입구에서 방까지 이동 --> 탐색

- 문마다 양방향으로 연결하는 길이 --> 그래프

- 최대한 입구에서 먼 방까지의 거리 --> 모든 그래프 탐색을 통해 최댓값 탐색 --> DFS

*BFS를 활용할 수도 있으나 최단거리를 이용하는 조건이 없으므로 DFS를 활용하는 것이 효율이 좋음

 

✅ 풀이

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

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

for _ in range(n-1):     # 조건: n-1개의 길로 오고갈 수 있다
  a, b, c = map(int, input().split())
  graph[a].append((b, c))   # 양방향
  graph[b].append((a, c))

answer = 0

def dfs(v, cost):
  global answer
  visited[v] = True
  
  answer = max(answer, cost)    # 기존과 최대값 비교

  for c, m in graph[v]:   # 각 노드에 연결되어 있는 노드마다
    if not visited[c]:
      dfs(c, cost + m)    # 현재까지 다다른 길이에서 길의 길이를 더하고

dfs(1, 0)     # 1이 입구인데 1에서 시작, 처음 비용은 0
print(answer)