개구리

우물 안 개구리

이제 비트마스킹은 그만 풀어야겠다. 2001번 보석줍기 문제는 주어진 테스트 케이스가 많이 없었고 오류를 찾지 못해서 5시간은 걸린 것 같다.

#보석줍기 bitmasking
from collections import deque

def bitCount(bit):
    count=0
    while bit>0:
        count+= 0b1 & bit
        bit = bit>>1
    return count

N,M,K= map( int, input().split() )
path=[[]for _ in range(N+1)]
diamond=[]

for _ in range(K):
    l = int(input())
    diamond.append(l)
for _ in range(M):
    a,b,c = map( int, input().split() )
    path[a].append((b,c))
    path[b].append((a,c))

# visited=[위치][보석]
visited=[ [-1 for _ in range(1<<K)] for _ in range(N+1) ] # 1 000 000 000 000 00
visited[1][0]=0
tmp=0

q=deque([[1,0]])
while (q):
    last,have = q.popleft()
    num=bitCount(have)# 현재 보석 가지고 있는 개수
  
    for island, weight in path[last]: # last에서 모든 아일랜드로 돌려보자
        if weight >= num and weight>0 : 
                    
            if visited[island][have]==-1:
                visited[island][have]=0
                q.append([island, have])
                
            if island in diamond :
                newhave=have|1<<(diamond.index(island))
                if visited[island][newhave]==-1:           
                    # have=newhave 이거 때문에 계속 오류 발생했다!!
                    visited[island][newhave]=0
                    q.append([island, newhave])
            
            
print(max(bitCount(i) for i in range(1<<K) if visited[1][i]==0))

n개의 섬을 BFS를 돌려가며 섬에 방문할 때마다 어떤 종류의 보석을 갖고 왔는 지 방문표시를 한다. 보석의 종류를 비트마스킹 기법을 통해 표현한다. 보석은 최대 14개만 존재하므로 14bit로 모든 경우를 표현할 수 있다.

구현

  1. 다음 섬으로 넘어가기 전 방문표시가 되어있거나 다리가 버틸 수 있는 무게 c보다 보석의 개수가 많다면 방문하지 않는다.
  2. 방문한 적이 없는 경우 queue에 넣고 BFS를 돌린다.
  3. 보석이 있는 섬을 지날 때 해당 섬에서 보석을 줍는 경우와 줍지 않는 경우 모두 queue에 넣고 BFS를 돌린다. 더 큰 범주의 방문한 적이 없는 경우에 실행되는 if문을 앞에 배치함으로써 두 경우 모두 queue에 넣을 수 있다.

보석의 개수

다리를 지날 때마다 현재 가지고 있는 보석의 개수를 알아야한다. 비트마스킹으로 표현한 보석들 중 1으로 표현된 비트의 개수를 알아야한다. 파이썬에는 이진수의 1로 마크된 비트를 카운트 할 수 있는 내장 함수가 없다. 비트 연산을 통해 1로 마크된 비트의 개수를 구하는 함수를 작성했다.

댓글남기기

참고