[Python/파이썬] 백준 1194번: 달이 차오른다, 가자

문제

 

풀이

비트 마스킹을 사용해 풀었다.

아직 방문하지 않은 상태 : 0b0

키 없음 : 0b1

a키 : 0b10

b키 : 0b100

c키 : 0b1000

a, c키 : 0b1010

...

이런 식으로 방문 여부를 기록했다.

 

또한 haveKey에 민식이가 보유한 열쇠 정보를 비트 마스킹했다.

키 없음 : 0b1

a키 보유 : 0b11

b키 보유 : 0b101

a, b키 보유 : 0b111

...

 

만약 a, b키를 가진 민식이가 좌표(x, y)에 방문하려 한다.

하지만 해당 좌표에 이미 a, b, c키를 소유한 채로 방문한 적이 있다면 방문할 필요가 없다.

if (visited[ni][nj] | haveKey) == visited[ni][nj]: continue

 

 

아래 링크를 참고하면 이해하기 쉽다.

https://studyandwrite.tistory.com/325

[Python] 비트마스크(Bit Mask)

 

코드

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

key = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':6}
door = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6}

n, m = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(n)]
visited = [[0] * m for _ in range(n)]

def condition(ni, nj):
    return ni < 0 or ni >= n or nj < 0 or nj >= m or graph[ni][nj] == '#'

def bfs(y, x):
    q = deque()
    q.append((y, x, 1, 0))
    visited[y][x] |= (1 << 0)
    dir = ((0, 1), (0, -1), (1, 0), (-1, 0))
    
    while q:
        i, j, haveKey, cnt = q.popleft()
        if graph[i][j] == '1':
            print(cnt)
            return
        
        for dy, dx in dir:
            ni, nj = i + dy, j + dx
            if condition(ni, nj):   continue
            if (visited[ni][nj] | haveKey) == visited[ni][nj]: continue
            if 'A' <= graph[ni][nj] <= 'F':
                if not (haveKey & (1 << door[graph[ni][nj]])): #키가 없는 경우
                    continue
            if 'a' <= graph[ni][nj] <= 'f':
                q.append((ni, nj, haveKey | (1 << key[graph[ni][nj]]), cnt + 1))
                visited[ni][nj] = (haveKey | (1 << key[graph[ni][nj]]))
                continue
            q.append((ni, nj, haveKey, cnt + 1))
            visited[ni][nj] = haveKey
    print(-1)
            
    
for i in range(n):
    for j in range(m):
        if graph[i][j] == '0':
            bfs(i, j)
            break

 

마무리

골드 1 문제여서 많이 쫄았는데 생각보다 풀만 했다. (방문 처리에서 시간을 꽤 잡아먹긴 했지만...)

 

노래가 엄청 좋다 ㅎ

https://www.youtube.com/watch?v=wG2lDphHVR8