[python] 백준 - 15971 (두 로봇)

2026.01.20ko 0 시리즈 · 알고리즘 #알고리즘

골드4 문제이며, 제한 시간은 2초이다.

문제

해결 과정

로봇 두 개를 움직이며 통신하기 위한 최단거리를 찾아야한다. 생각한 방식은 DFS를 이용해서 로봇 하나를 움직이고, 그 단계마다 BFS를 이용해서 다른 로봇에서부터 DFS로 움직인 로봇까지의 거리를 측정하려고 했다.

이 방식은 당연하게도 시간초과가 나서 23점을 받았따..

따라서 DP의 타뷸레이션 방식으로 로봇 b에서 모든 노드 사이의 거리를 BFS 한 번으로 DP테이블에 저장해놓고, DFS에서 사용하는 방식으로 코드를 개선했다.

풀이

from collections import deque

def bfs():
  queue = deque()
  queue.append((b, 0))
  dp[b] = 0

  while queue:
    t, v = queue.popleft()

    for x in graph[t]:
      if dp[x[0]] == -1:
        dp[x[0]] = v + x[1]
        queue.append((x[0], dp[x[0]]))

def dfs(a):
  global answer
  stack = []
  stack.append((a, 0, 0))
  visited = [False] * (n + 1)
  visited[a] = True
  while stack:
    t, v, max_len = stack.pop()
    answer = min(answer, v + dp[t] - max_len)
      
    for x in graph[t]:
      if not visited[x[0]]:
        n_len = max(max_len, x[1])
        stack.append((x[0], v + x[1], n_len))
        visited[x[0]] = True
    
n, a, b = map(int, input().split())
if n == 1 or a == b:
  print(0)
  exit(0)

graph = [[] for _ in range(n + 1)]
dp = [-1] * (n + 1)
answer = float('inf')
for _ in range(1, n):
  x, y, v = map(int, input().split())
  graph[x].append((y, v))
  graph[y].append((x, v))
bfs()
dfs(a)
print(answer)

아직 댓글이 없습니다.

문제

해결 과정

풀이

댓글

댓글 쓰기