[BOJ/백준] 15971 두 로봇 파이썬

문제 링크 : https://www.acmicpc.net/problem/15971

15971번: 두 로봇

문제는 그냥 BFS 문제이다.

두 로봇이 통신하기 위해선 이웃한 두점으로 로봇이 이동해야한다.

이때 드는 비용의 최솟값을 구해야한다.

한가지 주의할 점은 두 로봇이 같은 위치에 있을 수 있다는 것이다. 이부분을 체크해줘야한다.

 

처음에는 BFS를 두번 돌렸다.

그래서 한 로봇에서 BFS를 돌리면서 각 점까지의 최소값을 저장했다.

그리고 다른 로봇에서 BFS를 돌면서 해당 점까지의 이동 거리와 이전 로봇이 돌면서 구한 이동거리의 합으로 정답을 구하는 식으로 했다.

 

처음에는 한 지점을 오는 길이 여러 길이 있을 수 있다고 생각해서 저런식으로 구현했다.

근데 풀고 다른 사람 코드를 보고 문제를 다시 보니

"임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다."

두 지점 사이의 경로는 유일하다고 나와있었다.

저부분을 제대로 이해하지 않고 넘어가서 빙빙 돌아서 문제를 풀었다.

그 코드는 아래와 같다.

from sys import stdin
from collections import deque

input = stdin.readline
INF = 9876543210
n,start,end = map(int, input().split())
adj_list = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b,c = map(int, input().split())
    adj_list[a].append((b,c))
    adj_list[b].append((a,c))

answer = INF
visited1 = [INF] * (n + 1)
visited2 = [INF] * (n + 1)

def solv():
    if start==end:
        print(0)
    else:
        bfs(start,visited1,0)
        bfs(end,visited2,1)
        print(answer)

def bfs(s,visited,typ):
    global answer
    q = deque([(s,0)])
    visited[s] = 0
    while q:
        now,total = q.pop()
        if visited[now] != total:
            continue
        for nxt,cost in adj_list[now]:
            if typ == 1:
                answer = min(answer, visited1[nxt]+total)
            if visited[nxt] == INF or visited[nxt] > visited[now]+cost:
                visited[nxt] = visited[now]+cost
                q.appendleft((nxt,total+cost))
solv()

 

두 지점 사이의 경로는 유일하므로 한쪽에서 BFS를 진행한다.

그리고 중간에 가중치가 가장 큰 두곳에서 만나서 통신을 하면 최소비용으로 통신을 할 수 있다.

그래서 한쪽에서 시작에 끝지점까지 가면서 거리의 합을 구하고 중간중간에 가장 큰 비용을 저장한다.

그리고 마지막에 거리의 합과 가장 큰 비용을 빼면 답이 된다.

 

from sys import stdin
from collections import deque

input = stdin.readline
n,start,end = map(int, input().split())
adj_list = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b,c = map(int, input().split())
    adj_list[a].append((b,c))
    adj_list[b].append((a,c))

def solv():
    visited = [False]*(n+1)
    q = deque([(start,0,0)])
    visited[start] = True
    while q:
        now,total,max_cost = q.pop()
        if now == end:
            print(total-max_cost)
            return
        for nxt,cost in adj_list[now]:
            if not visited[nxt]:
                visited[nxt] = True
                q.appendleft((nxt,total+cost,max(max_cost,cost)))
solv()