오늘은 금요일. 코딩하기엔 좋지 않은 요일이다.
놀고 싶다.. 그리고 내일 코드포스 contest 예정이니깐 오늘은 잠깐 쉬어도 되지 않을까 자기합리화 중이다.
그래도 그냥 놀기엔 허전해서 풀었던 문제 중 쉽지만 흔하지는 않은 문제 하나 골라서 풀이를 적어볼까 한다.
BOJ 13168 - 내일로 여행 링크
(2022.08.12 기준 G3)
(치팅은 하지마..! 근데 이건 치팅하지마라고 하기엔 너무 쉽다)
문제
N개의 도시와 K개의 도시 간의 교통수단이 있고 M개의 도시를 차례대로 여행한다고 했을 때
내일로 티켓을 살 때와 사지 않을 때의 가격 비교
알고리즘
기본적으로 '플로이드-워셜'을 이용해야 한다. 간선들의 가중치가 다르며, 중복 방문이 가능하기 때문에 목적지까지 어딜 거치던 가장 저렴한 비용을 구해야 한다.
그리고 말은 거창한 '해시를 이용한 집합과 맵'.
도시나 교통 수단이 인덱스로 나오지 않고 고유 이름으로 나오기 때문에 그 이름에 대한 맵을 만들어줘야 한다. 파이썬에선 딕셔너리로 만들면 된다.dictionary = {'BoYangKu': 0, 'I': 1, 'Wanna': 2, 'Go': 3, 'Home': 4}
풀이
먼저 도시 이름을 입력받을 때, 그 도시 이름마다 인덱스를 지정해줘야 한다.
map.put("Seoul", 0) # java dictionary['seoul'] = 0 # python이런 느낌으로다가? 0부터 차례대로 지정해주자.
그리고 M개의 방문해야 하는 도시를 입력받는데
도시 이름마다 인덱스를 지정해준 맵이나 딕셔너리를 이용하여
이름이 아닌 인덱스로 저장해주자.root = [] for city in input().split(): root.append(dictionary[city])그리고 내일로 티켓을 샀을 때와 사지 않았을 때의 경로 별 비용을 담을 행렬 2개를 만들어주자.
플로이드-워셜을 돌릴 행렬.이제 여행 경로를 차례대로 입력받을 것이다.
먼저 시작 도시 S와 도착 도시 E는 인덱스로 바꿔 놓는다. 그리고 티켓 없는 경로를 먼저 갱신해주자.
min 함수를 써도 되고 if 문으로 직접 비교를 해도 되니깐 S-E 경로를 제일 저렴한 비용으로 갱신하자.그 다음은, 티켓 있는 경로를 갱신해주자.
먼저 교통 수단이 무궁화나 ITX 종류일 경우 무료이므로 0으로.
S-Train이나 V-Train이면 비용을 2로 나눈 값과 비교해서 더 적은 비용으로.
위 두 경우에 포함되지 않으면 비용과 비교해서 더 적은 비용으로.if t in ['Mugunghwa', 'ITX-Saemaeul', 'ITX-Cheongchun']: railro[s][e] = 0 railro[e][s] = 0 elif t in ['S-Train', 'V-Train']: if railro[s][e] > c / 2: railro[s][e] = c / 2 railro[e][s] = c / 2 else: if railro[s][e] > c: railro[s][e] = c railro[e][s] = c그리고 갱신해줄 때, 간선은 양방향이다.
한국에는 두 도시 사이를 오갈 수 있는 K개의 교통수단이 있습니다.
교통 수단 입력이 끝나면 티켓 별 경로 정보를 담은 행렬 2개를 플로이드-워셜 돌리자. 이 알고리즘에 대한 설명은 생략.for k in range(N): normal[k][k] = 0 railro[k][k] = 0 for i in range(N): for j in range(N): normal[i][j] = min(normal[i][j], normal[i][k] + normal[k][j]) railro[i][j] = min(railro[i][j], railro[i][k] + railro[k][j])별거 없다. 그냥 루프마다 두 행렬 같이 돌리면 된다.
이제 방문해야 하는 도시 차례대로 티켓 유무 별 가격을 계산해준 뒤, 비교하여 답을 출력하면 된다. 참 쉽죠?
코드
import sys; input = sys.stdin.readline
from math import inf
N, R = map(int, input().split())
cities = set(input().split())
N = len(cities)
ctoi = {city: i for i, city in enumerate(cities)} # 도시 별 인덱스 지정
M = int(input())
root = list(map(lambda x: ctoi[x], input().split())) # 방문해야 하는 도시를 인덱스로 바꿔서 저장
normal = [[inf] * N for _ in range(N)] # 티켓 없는 경로
railro = [[inf] * N for _ in range(N)] # 티켓 있는 경로
for _ in range(int(input())):
t, s, e, c = input().split()
s = ctoi[s]
e = ctoi[e]
c = int(c)
if normal[s][e] > c:
normal[s][e] = c
normal[e][s] = c
if t in ['Mugunghwa', 'ITX-Saemaeul', 'ITX-Cheongchun']:
railro[s][e] = 0
railro[e][s] = 0
elif t in ['S-Train', 'V-Train']:
if railro[s][e] > c / 2:
railro[s][e] = c / 2
railro[e][s] = c / 2
else:
if railro[s][e] > c:
railro[s][e] = c
railro[e][s] = c
# 플로이드-워셜
for k in range(N):
normal[k][k] = 0
railro[k][k] = 0
for i in range(N):
for j in range(N):
normal[i][j] = min(normal[i][j], normal[i][k] + normal[k][j])
railro[i][j] = min(railro[i][j], railro[i][k] + railro[k][j])
# 티켓 유무에 따른 가격 계산
normalCost = railroCost = 0
for i in range(M - 1):
normalCost += normal[root[i]][root[i + 1]]
railroCost += railro[root[i]][root[i + 1]]
# 티켓 유무에 따른 가격이 같아도 'No' 출력해야 함
print('Yes') if railroCost + R < normalCost else print('No')여담
귀찮지만 쉬운 문제였다. 그래도 이런 친근한(?) 문제 너무 좋지 않은가..?
내일로 여행 또 가고 싶다. 딱 한번 가봤는데 정말 추억이다. 어리니깐 가능한 일정이었고 그만큼 힘들지만 재밌었던 여행이었다.어찌됐든 일단 지금은 얼른 집가고 쉬고 싶다!
이번 포스팅 끝!
