| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 13683 | 7025 | 5670 | 49.881% |
문제
예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.
각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.
https://upload.acmicpc.net/ef3a5124-833a-42ef-a092-fd658bc8e662/-/preview/
주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번,2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.
입력
첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.
둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.
세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.
지역의 번호는 1이상 n이하의 정수이다. 두 지역의 번호가 같은 경우는 없다.
출력
예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.
답안
import sys
import math
# initialize variables
v, available_moves, e = map(int, sys.stdin.readline().split())
items = [0] + list(map(int, sys.stdin.readline().split()))
distances = [[math.inf for _ in range(v+1)] for _ in range(v+1)]
for i in range(1, v+1):
for j in range(1, v+1):
if i == j:
distances[i][j] = 0
for _ in range(e):
source, destination, weight = map(int, sys.stdin.readline().split())
distances[source][destination] = min(
distances[source][destination], weight)
distances[destination][source] = min(
distances[destination][source], weight)
# floyd-warshall algorithm
for k in range(1, v+1):
for i in range(1, v+1):
for j in range(1, v+1):
distances[i][j] = min(
distances[i][j], distances[i][k] + distances[k][j])
# find answer
answer = 0
for i in range(1, v+1):
sum = 0
for j in range(1, v+1):
if math.isinf(distances[i][j]) or distances[i][j] > available_moves:
continue
sum += items[j]
answer = max(answer, sum)
print(answer)풀이
처음에 생각했던 풀이는 DFS였다.
노드 수와 엣지 수가 그렇게 많지 않으니, 모든 노드를 각각 시작점으로 하는 DFS를 돌려, 수색 범위 안에 있는 모든 노드를 탐색하면 되지 않을까 하는 생각을 했었다.
하지만 이 생각은 틀린 생각이었다. 각 노드 간의 weight가 동일한 상황에서는 그렇게 풀어도 됐겠지만, 노드 간의 weight가 각각 달라 이렇게 한다면 최소 경로를 찾을 것이라는 보장이 없기 때문이다.
최소 경로가 중요한 이유는 아래와 같다.
만약 아래와 같은 그래프가 있고, 노드 A에서부터 탐색을 시작한다고 가정하자.
[노드A] ──2── [노드B] ──2── [노드C] ──5── [노드 D]
└──────────────3─────────────┘노드 A, 노드 B, 노드 C 순서대로 탐색을 진행한 뒤, 노드 A→노드 C 탐색을 진행하려고 하면, 노드 C는 A→B→C에서 이미 방문한 노드이기 때문에 DFS에서는 노드 C의 최소 경로가 4가 되어 버린다.
만약 수색 범위가 3인 상황에서 위와 같은 문제가 발생한다면, 문제의 답도 다르게 나오게 될 수 있을 것이다.
예전에도 0-1 BFS 문제를 일반적인 BFS로 풀려다가 낭패를 본 적이 있었는데, 이번에도 비슷한 결이었던 것 같다.
이렇게 weight가 있는 경우에는 일반적인 DFS, BFS가 아닌 그래프 최소경로 알고리즘을 먼저 떠올리도록 해야겠다.
물론 DFS로 구현한다고 하더라도 만약 이미 방문했던 노드인 경우에 아이템의 개수를 갱신하지 않는 방법이 있을 수 있겠으나, 나는 아예 이전 구현을 모두 갈아엎고 다른 풀이를 해보기로 했다.
노드의 수가 작아 플로이드 워셜 알고리즘을 사용할 수 있을 것 같았고, 플로이드 워셜 알고리즘이 구현이 훨씬 쉬웠기 때문이다.
# floyd-warshall algorithm
for k in range(1, v+1):
for i in range(1, v+1):
for j in range(1, v+1):
distances[i][j] = min(
distances[i][j], distances[i][k] + distances[k][j])그래서 플로이드 워셜 알고리즘을 돌려 모든 노드 간 최소 거리를 구했고, 이를 통해 최소 거리가 수색 범위 안에 있는 모든 노드들의 아이템의 개수의 합을 구했다.
