[파이썬] 백준 2001 : 보석줍기 (플레5)

[파이썬] 백준 2001 : 보석줍기 (플레5)

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

 

---

풀이

방향성 생각

• 전형적인 BFS + bitmask
• $2^K*N$배열을 BFS로 방문해야해서 효율적으로 처리해야한다.
• state를 bit로 계산하지 않고, 문자열로 변환 후 카운팅하면 코스트가 꽤나 있다.

 

---

전체코드

from collections import deque
import sys
input = sys.stdin.readline

N,M,K = map(int,input().split())
dia = {}
for i in range(K):
    dia[int(input())-1] = i


G = [[] for _ in range(N)]
for _ in range(M):
    a,b,limit = map(int,input().split())
    G[a-1].append((b-1,limit))
    G[b-1].append((a-1,limit))

# 현재 들고있는 개수 체크
def check(state):
    count = 0
    while state:
        count += state&1
        state >>= 1
    return count

# 시작섬 보석 줍는 경우, 안줍는 경우 (사실 안줍고 마지막에 줍는게 낫다)
Q = deque([(0,0)])
V = [[-1]*N for _ in range(1<<K)]
V[0][0] = 0
if 0 in dia:
    Q.append((0,1<<dia[0]))
    V[1<<dia[0]][0] = 1

while Q:
    x,s = Q.popleft()
    for nx,limit in G[x]:
        # 제한 넘어서 못건너면 다음
        if check(s) > limit:
            continue
        # 방문하지 않은 곳 방문
        if V[s][nx] == -1:
            V[s][nx] = V[s][x]
            Q.append((nx,s))
        # 보석 있는 섬 방문 안했으면 방문
        if (nx in dia):
            ns = s|(1<<dia[nx])
            if not s&(1<<dia[nx]) and V[ns][nx] == -1:
                V[ns][nx] = V[s][x] + 1
                Q.append((nx,ns))
print(max(V[s][0] for s in range(1<<K)))

---

코멘트

• .