[백준 2001번] 보석 줍기 (Python3)

import sys
input = sys.stdin.readline

def DFS(now,bit,cnt):
  if graph[now][0] >= cnt:
    DP[now][bit] = cnt
  for next in range(1,K+1):
    if bit&(1<<next) or graph[now][next]<cnt:
      continue
    if not DP[next][bit|(1<<next)]:
      DFS(next,bit|(1<<next),cnt+1)
    DP[now][bit] = max(DP[now][bit],DP[next][bit|(1<<next)])

def makegraph():
  newgraph = [[0]*(K+1) for i in range(K+1)]
  for i in range(K+1):
    for j in range(K+1):
      newgraph[i][j] = graph[jewel[i]][jewel[j]]
  return newgraph

N,M,K = map(int,input().split())
jewel = [0]+[int(input())-1 for i in range(K)]

graph = [[-1]*N for i in range(N)]
for i in range(M):
  x,y,w = map(int,input().split())
  graph[x-1][y-1] = graph[y-1][x-1] = w
for i in range(N):
  graph[i][i] = 100
for k in range(N):
  for i in range(N):
    for j in range(N):
      if graph[i][j] < min(graph[i][k],graph[k][j]):
        graph[i][j] = min(graph[i][k],graph[k][j])

graph = makegraph()
result = 0
DP = [[0]*(1<<(K+1)) for i in range(K+1)]
DFS(0,1,0)
print(DP[0][1])

비트마스킹을 이용한 DP + 플로이드 워셜을 이용하여 해결하였다.

 

풀이를 우선 설명하면,

1. 플로이드 워셜을 이용하여, 모든 섬 간에 그래프를 찾아준다. 이때 그래프의 갱신은 간선의 가중치의 최솟값의 크기가 클 때 일어난다.

2. 보석이 있는 K개의 섬과 1번 섬을 가지고 그래프를 간소화시킨다. (N*N 크기의 인접행렬을 (K+1)*(K+1)로 간소화)

3. 외판원 순회 [백준 2098번] 외판원 순회 (Python3) (tistory.com) 방식으로 비트마스킹을 이용한 DP로 순회할 수 있는 섬의 최댓값을 구한다.

4. 결과를 출력한다.

 

문제에서 N의 크기가 최대 100으로 매우 작기 때문에 플로이드-워셜을 응용해서 섬간에 이동할 수 있는 최대보석개수를 찾는것이 핵심이다. 이것만 성공하면, 이후는 외판원 순회 문제를 풀었다면 쉽게 해결할 수 있다.

 

 

오늘의 교훈) N이 작을떄는 플로이드-워셜이 최고다