15971. 두 로봇

사용한 알고리즘 / 자료구조

1. 우선순위 큐 (heapq)
2. 트리
3. 다익스트라 알고리즘

접근한 방식

두 로봇 사이의 최단 거리를 계산해야 합니다.

일반적인 다익스트라 방식으로 접근했습니다.

 

단, 현재 사용한 경로에서 '가장 긴 경로'를 제외해야 하므로 두 로봇 사이의 최단 경로 정보를 저장해야 합니다. 

배열을 사용해 이를 구현합니다. 

• path: 접근 경로를 저장하는 리스트. index == 노드 번호, value == 출발지
• path_distance: 경로의 길이를 저장하는 리스트. index == 노드 번호, value == 경로의 길이.

다익스트라 연산을 끝마친 후 경로를 역추적합니다.

로봇1에서 로봇2까지의 거리를 계산한 뒤 , 가장 길었던 경로(worst_path)를 거리에서 제합니다. 

 

어려웠던 점

다익스트라 연산을 하며 경로 역추적. 

 

느낀 점 

경로 역추적을 구현하는 데에 괜찮은 문제들입니다.

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

9019번: DSLR

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

13913번: 숨바꼭질 4

 

풀이했을 당시의 백준 티어

2021-10-25, 골드 1

 

실행시간, 메모리, 언어

632ms, 69476kb, Python3  

 

import sys
import heapq

# 1. 입력
# a. 노드의 갯수
# b. 로봇1의 좌표
# c. 로봇 2의 좌표
N, ROBOT_1, ROBOT_2 = map(int, sys.stdin.readline().split())

# 2. 선언
# 1) 다익스트라 연산을 위한 배열 선언
total_distance = [-1] * (N + 1)     # -1로 초기화(INF대신)
total_distance[ROBOT_1] = 0         # 출발지 초기값을 0으로 선언.

# 2) 경로 역추적을 위한 배열 선언
path = [0] * (N + 1)            # 경로를 저장할 배열 선언. index 가 정점 번호, value 가 '어디에서 왔는지'
path_distance = [0] * (N + 1)   # 해당 경로를 사용할 때 '경로' 의 길이값.

# 2-1. 경로 입력
connections = [[] for _ in range(N + 1)]    # 연결 리스트 선언
for _ in range(N - 1):
    node1, node2, distance = map(int, sys.stdin.readline().split())
    connections[node1].append((distance, node2))      # 방향성이 없는 간선이므로
    connections[node2].append((distance, node1))      # node1, node2에 모두 삽입.
    

# 3. 연산
# 1) 다익스트라 연산을 위해 큐 선언. 
priority_que = [(0, ROBOT_1)]

# 2) 다익스트라 연산 시작.
while priority_que:    # 큐에 값이 남아있는 동안
    
    # (1) 현재 좌표와 거리 확인.
    current_distance, current_node = heapq.heappop(priority_que)

    # a. 가지치기
    # 내가 현재 확인하는 지점에 더 빨리 도착할 수 있는 방법이 존재한다면
    if total_distance[current_node] < current_distance:
        continue

    # (2) 다음 지점 확인
    for next_distance, next_node in connections[current_node]:

        # a. 다음 지점까지의 거리. 
        distance_sum = current_distance + next_distance

        # i) 가지치기. 
        # next_node 에 방문한 적이 있으며 (초기값이 아니며)
        # 현재 방법보다 더 빨리 도착할 방법이 존재한다면 
        if total_distance[next_node] != -1 and total_distance[next_node] <= distance_sum:
            continue

        # b. 기록 및 큐에 삽입. 
        total_distance[next_node] = distance_sum    # 시작지점으로부터의 거리. 
        path[next_node] = current_node              # 경로 입력. 
        path_distance[next_node] = next_distance    # 경로의 길이 입력. 
        heapq.heappush(priority_que, (distance_sum, next_node))    # 큐에 삽입. 

# 3) 경로 찾기 연산
path_index = ROBOT_2    # 끝 지점에서부터 조회. 
distance_total = total_distance[ROBOT_2]    # 거리의 총합
worst_path = 0              # 가장 긴 길의 길이를 저장할 변수.

while path_index:
    current_path_distance = path_distance[path_index]   # 현재 지점으로 오는 데 사용한 경로가
    if current_path_distance > worst_path:              # 지금까지 조회했던 경로들보다 길다면
        worst_path = current_path_distance              # 갱신. 

    path_index = path[path_index]                       # 인덱스 번호 업데이트.


# 4. 출력
print(distance_total - worst_path)