[백준/2001] 보석 줍기 (Python)

Problem : https://www.acmicpc.net/problem/2001

2001번: 보석 줍기

 

Difficulty : Gold 1

 

Status : 00:29:51

 

Time : Solved

 

---

 

문제 설명

 

n(1 ≤ n ≤ 100)개의 섬이 m(1 ≤ m ≤ 1,000)개의 다리로 연결되어 있다. 각각의 다리는 서로 다른 두 섬을 연결하고 있으며, 서로 다른 두 섬은 최대 한 개의 다리로만 직접 연결되어 있다. 각각의 다리들의 튼튼한 정도는 서로 달라서, 각각의 다리마다 견딜 수 있는 무게의 제한이 다를 수 있다.

섬들 중, K(1 ≤ K ≤ 14)개의 서로 다른 섬에 각각 한 개씩 보석이 있다. 당신은 1번 섬에서 빈손으로 출발하여 최대한 많은 보석을 줍고 1번 섬으로 돌아오려 한다. 주의할 것은, 보석을 너무 많이 줍다 보면 다리를 건널 때 다리가 무게를 견디지 못하고 무너질 수 있다는 점이다. 따라서 당신은 다리가 무너지지 않는 한도 내에서 보석을 주워야 한다.

한 번 지난 적이 있는 다리와 섬을 여러 번 지날 수 있으며, 보석이 있는 섬을 지날 때에 그 보석을 줍지 않을 수도 있다고 하자.

 

입력 및 출력

 

입력

 

첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 b번 섬이 다리로 연결되어 있는데, 그 다리가 최대 c개의 보석만을 견딜 수 있다는 의미이다. 예를 들어 c가 2라면, 그 다리를 지날 때 보석을 0, 1, 2개 가지고 있어야 한다는 의미이다. 3개 이상의 보석을 가지고 그 다리를 지나려고 하면 다리가 무너진다.

 

출력

 

첫째 줄에 주울 수 있는 보석의 최대 개수를 출력한다.

 

입력 예시

 

6 7 5
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1

 

출력 예시

 

4

 

 

---

 

풀이

 

그래프 문제를 풀 때, 현재 섬의 위치에서 저장되어야 할 정보는 지금까지 방문하여 주워 왔던 보석들이 될 것이다. 보석의 개수뿐만 아니라 보석의 위치 역시 중요하므로, 이 보석의 개수, 위치를 동시에 나타낼 수 있는 비트마스킹 연산이 필요하다. 이 비트마스킹 연산을 거쳐 최종적으로 초기 지점으로 돌아온 값 중 가장 큰 값을 찾아내면 되겠다.

 

 

풀이 코드

from collections import defaultdict, deque
import sys
input = sys.stdin.readline
MAX = float('inf')

n, m, K = map(int, input().split())
jewelry = [0]*n
for i in range(K) :
  jewelry[int(input())-1] = i+1

edge_dict = defaultdict(list)
for _ in range(m) :
  a, b, c = map(int, input().split())
  edge_dict[a-1].append((b-1, c))
  edge_dict[b-1].append((a-1, c))

visited = [[False]*(1 << K) for _ in range(n)]
visited[0][0] = True
q = deque([(0, 0, 0)])
ans = 0

while q :
  node, cnt, visit = q.popleft()
  if node == 0 and visit :
    ans = max(ans, cnt)
    continue
  for nxt, cost in edge_dict[node] :
    if cost < cnt :
      continue
    if not visited[nxt][visit] :
      visited[nxt][visit] = True
      q.append((nxt, cnt, visit))
    if jewelry[nxt] :
      jidx = jewelry[nxt]-1
      if not visit & (1 << jidx) and not visited[nxt][visit | (1 << jidx)] :
        visited[nxt][visit | (1 << jidx)] = True
        q.append((nxt, cnt+1, visit | (1 << jidx)))
print(ans)

풀이 완료!