[백준] 13168번: 내일로 여행

문제

백준 - 13168번: 내일로 여행

분석

도시 정보들과 교통수단에 따른 티켓 정보들이 주어졌을 때, 내일로 티켓을 사는 것과 사지 않는 것 중 더 나은 판단을 하는 문제이다.

모든 경로에 대한 최단 거리(최소비용)를 구하는 문제이다.
도시의 수가 최대 100개 이므로 O(N^3)의 시간복잡도를 가진 플로이드 워셜 알고리즘을 사용한다.

N개의 도시 중 같은 이름이 있을 경우 같은 도시로 치기 때문에 set으로 중복된 것을 먼저 없애준다. 또한, 도시 이름 대신 인덱스를 이용하면 더 편하기 때문에 변환해줄 딕셔너리를 사용한다.
내일로를 이용하지 않을 경우는 graph에 저장하고, 내일로를 이용할 경우에는 nailro에 정보를 저장한다. 내일로일 경우에 type에 따라 cost를 조정하면 된다.
주의할 것은 '두 도시 사이를 오갈 수 있다'고 했으므로 양방향으로 입력받아야 된다.
이 부분을 놓쳐 오래걸렸다.

정보를 다 입력받으면 플로이드 워셜 알고리즘을 적용한다. 이 문제에서는 모든 도시가 갈 수 있음이 보장된다고 명시되어있다.

마지막에 내일로 티켓을 구매했을 경우 총 비용과, 구매하지 않았을 경우를 비교하여 내일로 티켓을 구매한 게 더 이득일 경우에만 'Yes'를 출력하고 그 외엔 'No'를 출력한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

N, R = map(int, input().split())
cities = list(set(input().rstrip().split()))
N = len(cities)
name = {}
for i in range(N):
    name[cities[i]] = i
M = int(input())
targets = list(input().rstrip().split())
INF = sys.maxsize
graph = [[INF]*N for _ in range(N)]
nailro = [[INF]*N for _ in range(N)]
for i in range(N):
    graph[i][i] = 0
    nailro[i][i] = 0
K = int(input())
for _ in range(K):
    type, s, e, cost = input().rstrip().split()
    cost = int(cost)
    graph[name[s]][name[e]] = min(graph[name[s]][name[e]], cost)
    graph[name[e]][name[s]] = min(graph[name[e]][name[s]], cost)
    if type == 'Mugunghwa' or type == 'ITX-Saemaeul' or type == 'ITX-Cheongchun':
        cost = 0
    elif type == 'S-Train' or type == 'V-Train':
        cost /= 2
    nailro[name[s]][name[e]] = min(nailro[name[s]][name[e]], cost)
    nailro[name[e]][name[s]] = min(nailro[name[e]][name[s]], cost)
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
            nailro[i][j] = min(nailro[i][j], nailro[i][k]+nailro[k][j])

ticket, noTicket = R, 0
for i in range(M-1):
    s, e = name[targets[i]], name[targets[i+1]]
    ticket += nailro[s][e]
    noTicket += graph[s][e]
print('Yes' if ticket < noTicket else 'No')

cost가 반 값이 되는 부분에서 소수점을 날렸었는데 0.5까지 계산해줘야 한다.

끝으로..

경우를 나눠서 생각하면 금방 쉽게 풀리는 문제였는데, 한 번에 하려다 오래걸렸다.