백준 [15971] 두 로봇 (Python3)

처음부터 꼬아서 생각했다가 복잡하게 푼 문제

경로를 계산하는 방법은 3가지가 있다.

1. A가 한 칸 뒤로 가고, B가 한 칸 앞으로 감.
2. B가 한 칸 뒤로 가고, A가 한 칸 앞으로 감.
3. A, B가 그냥 현재 위치에서 통신

 

위 3가지 경우를 고려하면 A부터 출발하든, B부터 출발하든 특정 간선 하나는 지나지 않는다.
이 간선은 바로 A부터 B 또는 B부터 A까지 가는 간선 중 가장 비용이 큰 간선이다.
이렇게 구한 총 비용 중, 가장 큰 비용을 빼면 답이 나온다.

 

 

나는 위 3가지 경우를 다 고려해서 A부터 B까지 모든 경로 구한뒤에 B부터 탐색을 시작해,
매 지점마다 저 3가지를 고려했다.
그래도 N의 범위가 작기 때문에 통과는 됐지만 좋은 해결책은 아니었다.

from collections import deque

def solve(N, A, B, nodes):
    visit = [False] * (N + 1)
    visit[A] = 1
    q = deque([(A, 0, 0)])
    while q:
        here, total, maxC = q.popleft()
        if here == B:
            return total - maxC
        for there, thereC in nodes[here]:
            if visit[there]:
                continue
            visit[there] = True
            q.append([there, total + thereC, max(maxC, thereC)])
    return 0

def main():
    N, A, B = map(int, input().split())
    nodes = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v, c = map(int, input().split())
        nodes[u].append((v, c))
        nodes[v].append((u, c))
    print(solve(N, A, B, nodes))


if __name__ == "__main__":
    main()