[백준] 1956. 운동
Link 골드 4티어 문제
문제
V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.
당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.
도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.
입력
첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.
출력
첫째 줄에 최소 사이클의 도로 길이의 합을 출력한다. 운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력한다.
예제 입력 1
1
2
3
4
5
3 4
1 2 1
3 2 1
1 3 5
2 3 2
예제 출력 1
1
3
풀이
그래프와 DP를 사용하여 풀어야하는 문제로, 상당히 고난도의 문제라고 볼 수 있다.
인터넷에 검색해보 다익스트라 알고리즘, 플로이드 와샬 알고리즘을 사용하여 풀 수 있다고 하는데,
일단 이런거 다 집어치우고 직관적으로 어떻게 문제를 풀 수 있을지 생각해보도록 하자.
사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾는 것이 목표인데, 시작시점이 특정되지 않기 때문에 모든 마을을 시작지점으로 잡아 모든 경우의 수를 따져봐야 한다.
도로의 길이에 따라 출발지에서 도착지까지 간다고 했을 때, 어느 마을을 경유했다가 가는것이 빠를 수도 있고, 아닐 수도 있다.
따라서 각 마을에서 어느 마을까지 가는데 최단거리를 기록한다음 현 마을에서 현 마을로 돌아오는데 걸리는 최소 도로의 길이를 구하면 문제를 풀 수 있다.
이제 문제는 최단 거리를 어떤 방식으로 업데이트 해나갈 것인지 이다.
두가지 방법이 떠오르는데..
- 표를 작성하여 각 마을별 도로의 길이를 기록한 다음 어떤 마을을 경유해서 갔을 때와 곧바로 갔을 때의 도로의 길이를 비교해나가는 것
- 현 출발점부터 도착점와 도로의 길이를 계속 갱신해나가는 것
이러한 문제풀이 방식을 각각 플로이드 와샬, 다익스트라 알고리즘이라고 한다.
플로이드 와샬 알고리즘의 처리순서를 정리하면 아래와 같다. (현재 각 마을에서 다른 마을까지의 도로의 길이는 2차원 array로 정의되어있는 상태라고 하자)
- 마을 i에서 마을 j로 간다고 할 때, 마을 k를 거쳐가는 것과 마을 i에서 j로 곧바로 가는 것중 어떤게 더 도로의 길이가 짧은지 판단
- 더 짧을 때의 도로의 길이로 Update
- 마을 j가 마지막 마을일 때까지 반복
- 마을 i가 마지막 마을일 때까지 반복
- 마을 k가 마지막 마을일 때까지 반복
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# https://velog.io/@nkrang/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-1956-%EC%9A%B4%EB%8F%99-%ED%92%80%EC%9D%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC
# 주석이 참 깔끔하다..
vilige, edge = map(int, input().split())
#거리를 저장할 2d array
table = [[int(1e9)] * (vilige+1) for _ in range(vilige+1)]
for _ in range(edge):
x, y, c = map(int, input().split())
table[x][y] = c
#경유지 k, 출발지 i, 도착지 j
for k in range(1, vilige+1):
for i in range(1, vilige+1):
for j in range(1, vilige+1):
# i->j 가 짧은지 i->k->j가 짧은지를 검사한다.
if table[i][k] + table[k][j] < table[i][j]:
table[i][j] = table[i][k] + table[k][j]
answer = 1e9
for i in range(1, vilige+1):
#사이클은 결국 출발지와 도착지가 같은 경우이므로 i->i를 확인
answer = min(answer, table[i][i])
#최소값이 없으면 -1, 있으면 최소값을 출력
if answer == 1e9:
print(-1)
else:
print(answer)
다익스트라 알고리즘 (변형) 처리 순서는 아래와 같다.
- 1차원 배열에 [출발지, 도착지, 거리]를 heapq에 저장
- heapq의 Element를 하나씩 꺼내면서 현 도착지에서 갈 수 있는 다른 마을들을 찾아서 도착지와 거리를 Update 한다음 다시 Heapq에 추가한다.
- 출발지와 도착지가 같을 때 까지 반복
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import heapq as hq
vilige, edge = map(int, input().split())
graph = [[] for _ in range(vilige+1)]
#거리를 저장할 배열을 2차원으로
dist = [[1e9] * (vilige+1) for _ in range(vilige+1)]
heap = []
for _ in range(edge):
x, y, c = map(int, input().split())
graph[x].append([c, y])
dist[x][y] = c
#heap에도 비용, 출발지, 도착지 3개의 값을 넣어준다.
#유효한 경로 값을 다 넣어줌
hq.heappush(heap, [c, x, y])
while heap:
#최소 비용의 경로를 먼저 뽑아주고 (d:비용, s:출발, g:도착)
d, s, g = hq.heappop(heap)
#출발지와 도착지가 같다면 사이클
if s == g:
print(d)
break
#d 값이 이미 저장된 비용보다 크다면 넘겨버림 --> 최소를 찾으려는거니까
if dist[s][g] < d:
continue
#g에서 갈 수 있는 다른 마을들 확인
for nd, ng in graph[g]:
# 거리 업데이트
new_d = d + nd
# 경유지를 들렀다가는것이 더 짧은지 아닌지 확인
if new_d < dist[s][ng]:
dist[s][ng] = new_d
hq.heappush(heap, [new_d, s, ng])
else:
#heap 다 돌았는데 없다면 -1 --> 사이클이 없다.
print(-1)