문제
분석
지역 번호, 가진 아이템 수, 지역 번호간 거리에 대한 정보가 주어지고, 수색 범위 m이 주어진다.
낙하한 지역에서 거리가 수색 범위 m 이내의 모든 지역의 아이템을 습득할 때, 얻을 수 있는 최대 아이템 개수를 구하는 문제이다.
처음에 단순하게 DFS 풀이를 떠올리고 풀었지만, 9%에서 자꾸 틀렸다.
그래서 질문 게시판을 통해 사람들이 플로이드 워셜이나 다익스트라로 푼 것에 힌트를 얻어 나도 플로이드 워셜로 적용해보았다.
플로이드 워셜은 모든 지점과 지점 간에 최소 거리를 구할 수 있다.
n이 100 밖에 되지 않아서 충분히 시간안에 들어올 것이라 판단했다. O(N^3)
플로이드 워셜은 인접행렬로 구현하는 것이 편하다.
각 최소 거리를 모두 구하면 최소 거리가 m이하인지 판단하여 얻을 수 있는 최대 아이템을 구한다.
이렇게 끝냈으면 아쉬울 뻔했다. 처음에 시도한 DFS에서 실패한 이유가 DFS는 visited 배열을 하나 사용하기 때문에 한 경로에서 방문처리한 것이 다른 경로(경우)에 영향을 미칠 수 있다.
만약
(1) ... 1 -> 2 -> 3 -> 4
(2) ... 1 -> 3 -> 4
와 같은 경로가 있다고 치고 (1) 경로를 먼저 탐색을 끝냈을 경우, 3에 방문처리가 이미 되어있어서 (2) 경로를 진행할 때 무시 되어버린다.
연결된 간선마다 가중치가 다르기 때문에 어떤 경로가 더 최소 거리 인지 알 수 없기 때문에 (2)의 경로도 고려할 수 있는 방향으로 조정해야한다.
방법 -> 방문 처리 변형
x에 연결된 nx에 대한 dfs(nx)를 진행하고 난 다음, 해당 노드에 대해 방문을 False로 바꾼다. 이렇게 하면 모든 경로는 독립적이고, visited 배열이 다른 경로에 영향을 미치지 않게 된다.
def dfs(x, dist):
if dist > m:
return
visited[x] = True
can_get[x] = True
for nx, d in graph[x]:
if not visited[nx]:
dfs(nx, dist+d)
visited[nx] = False아래와 같이 x를 for문이 끝나고 False처리하는 경우도 가능하다.
def dfs(x, dist):
if dist > m:
return
visited[x] = True
can_get[x] = True
for nx, d in graph[x]:
if not visited[nx]:
dfs(nx, dist+d)
visited[x] = Falsevisited외에 한 번이라도 방문이 가능했던 곳을 저장해 줄 can_get배열을 따로 만들었다.
이 can_get이 True인 곳만 cnt에 더하였고, 최대값과 비교하여 ans를 갱신해나갔다.
코드 - 플로이드 워셜 풀이
해결언어 : Python
import sys
input = sys.stdin.readline
INF = sys.maxsize
n, m, r = map(int, input().split())
item = [-1]+list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
dist[i][i] = 0
for _ in range(r):
a, b, l = map(int, input().split())
dist[a][b] = l
dist[b][a] = l
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
ans = 0
for i in range(1, n+1):
cnt = 0
for j in range(1, n+1):
if dist[i][j] <= m:
cnt += item[j]
ans = max(ans, cnt)
print(ans)코드 - DFS 풀이
해결언어 : Python
import sys
input = sys.stdin.readline
INF = sys.maxsize
n, m, r = map(int, input().split())
graph = [[]for _ in range(n+1)]
item = [-1]+list(map(int, input().split()))
for _ in range(r):
a, b, l = map(int, input().split())
graph[a].append((b, l))
graph[b].append((a, l))
def dfs(x, dist):
if dist > m:
return
visited[x] = True
can_get[x] = True
for nx, d in graph[x]:
if not visited[nx]:
dfs(nx, dist+d)
visited[nx] = False
ans = 0
for i in range(1, n+1):
visited = [False]*(n+1)
can_get = [False]*(n+1)
dfs(i, 0)
cnt = sum(item[i] for i in range(1, n+1) if can_get[i])
ans = max(ans, cnt)
print(ans)
DFS 풀이가 40ms로 더 빠르게 나왔다.
끝으로..
처음 시도한 방법을 다시 시도해서 내 방식으로 푼 점이 뿌듯했다.
DFS에서 방문처리를 응용하여 모든 가능한 경로를 파악하는 방법을 알게 되어 좋았다.
