[백준/Python]13168: 내일로 여행

문제

https://www.acmicpc.net/problem/13168
백준 문제집 - 0x1C강 - 플로이드 알고리즘

 

알고리즘: 구현, 최단 경로, 해시를 사용한 집합과 맵, 플로이드-워셜

---

풀이

데이터를 문자열 형태로 저장해야해서 그렇지, 문제 자체는 단순한 플로이드 워셜 문제다.
다만 주의해야할 조건이 있다.

1. 50% 할인 처리 시, 값이 실수형으로 나올 수 있으므로 미리 처리해줘야함.
   • 방법 1: 실수형으로 계산 (/)
   • 방법 2: 모든 비용을 2배로 취급 -> 50% 할인 시 정수형으로 처리됨
2. 티켓을 중간에 구매할 경우도 따져야 함.
3. 시작도시-도착도시 값은 중복으로 주어질 수 있음. 최소비용으로 저장해야함.

 

즉, 여행 도시가 M개라면 1 ~ M-1 번째에서 티켓을 구매할 경우를 고려해야한다.

 

실행 순서는 다음과 같다.

1. 입력 데이터 처리
   • [시작도시][도착도시] 값이 이미 존재한다면, 비교 후 더 작은 값을 저장
2. 기본 값, 티켓 구입 시의 값을 따로 분리하여 플로이드 워셜 수행
   • 양방향으로 저장
3. 기본 값(티켓 X) 총 비용 계산
4. 중간에 티켓을 구매했을 경우의 총 비용 계산
   • 1 ~ M-1번째 도시(인덱스 기준으로 0 ~ M-2)를 하나씩 체크
   • (i번째 도시까지 기본으로 이동한 값 + 티켓값) + (i+1 ~ M번째 도시까지 티켓으로 이동한 값) 계산
   • 기존 계산값과 새로운 계산값을 매번 비교해가며 최솟값 갱신
5. 4번을 통해 얻은 최솟값(티켓 O)과, 기본 값을 비교
   • 티켓을 사는게 더 효율적이라면 "Yes", 아니면 "No" 출력

 

전체 코드

# 메모리: 33432KB / 시간: 720ms
from sys import stdin


input = stdin.readline
INF = int(1e9)

N, R = map(int, input().split())
R *= 2
data = set(input().rstrip().split())
cities = {d: i for i, d in enumerate(data)}

M = int(input())
trip_cities = [cities[city] for city in input().rstrip().split()]

# 🚨 그냥 정수 나눗셈 // 처리를 해주면 틀림...
# 해결방법 1. 실수형으로 계산, 2. 2배 해준뒤 // 사용
def calc(city, cost):
    if city in ("Mugunghwa", "ITX-Saemaeul", "ITX-Cheongchun"):
        return 0
    if city in ("S-Train", "V-Train"):
        return cost // 2
    return cost


ticket = [[INF] * N for _ in range(N)]
normal = [[INF] * N for _ in range(N)]
K = int(input())

for _ in range(K):
    T, S, E, cost = input().rstrip().split()

    S, E = cities[S], cities[E]
    cost = int(cost) * 2

    ticket_cost = calc(T, cost)
    ticket[S][E] = min(ticket_cost, ticket[S][E])
    ticket[E][S] = min(ticket_cost, ticket[E][S])

    normal[S][E] = min(cost, normal[S][E])
    normal[E][S] = min(cost, normal[E][S])

for k in range(N):
    for i in range(N):
        for j in range(N):
            ticket[i][j] = min(ticket[i][k] + ticket[k][j], ticket[i][j])
            normal[i][j] = min(normal[i][k] + normal[k][j], normal[i][j])

# 티켓을 사지 않았을경우의 비용
normal_cost = sum(normal[trip_cities[i]][trip_cities[i+1]] for i in range(M-1))


# 중간에 티켓을 구매할 경우를 고려해서 계산해야함.
def total_cost(start, cost):
    for i in range(start, M-1):
        cost += ticket[trip_cities[i]][trip_cities[i+1]]

    return cost

min_cost = INF

curr_cost = 0
for start in range(M-1):
    cost = total_cost(start, curr_cost) + R
    min_cost = min(cost, min_cost)
    curr_cost += normal[trip_cities[start]][trip_cities[start+1]]

print("Yes" if min_cost < normal_cost else "No")