[백준✨] 9328번 <열소> / Python 문제풀이 /

해답)

from collections import deque
import sys
sys.setrecursionlimit(10**8)

def input():
  return sys.stdin.readline().rstrip()

dir = [(0,1),(0,-1),(-1,0),(1,0)]

'''
@@@ 기능 함수 @@@
'''

def printBoard(board): # 보드 출력해보기 (디버깅용)
  print("--- printBoard ---")
  for line in board:
    for val in line:
      print(val, end="")
    print("")
  print("-----------------")

def parseKeys(keys): # 가지고 있는 키 목록 비트화 (b10000000000....)
  if keys == ['0']:
    return 0
  result = 1<<26
  for key in keys:
    result |= 1 << (ord(key) - ord('a'))
  return result

def canOpen(keys, target):
  return (1 << (ord(target) - ord('A'))) & keys != 0

def addKey(keys, key):
  return keys | (1 << (ord(key)-ord('a')))

def isNewKey(keys, key):
  return (1 << (ord(key) - ord('a'))) & keys == 0

def openAllDoor(keys): # 보드에 있는 문 중에 열 수 있으면 열어버린다. ('.'로 만들어버린다.)
  opens = []
  for r in range(R):
    for c in range(C):
      if board[r][c] == '.' or board[r][c] == '*' or board[r][c] == "$":
        continue
      if canOpen(keys, board[r][c]):
        opens.append((r,c))
        board[r][c] = '.'
  return opens

def getEnter(board, visited): # 가장자리를 탐색해서 들어갈 수 있는 입구 목록 반환 
  enter = []
  for c in range(C):
    for r in [0,R-1]:
      if board[r][c] != '*':
        enter.append((r,c))
        visited[r][c] = True
  for r in range(1, R-1):
    for c in [0,C-1]:
      if board[r][c] != '*':
        enter.append((r,c))
        visited[r][c] = True
  return enter   

'''
@@@ 코드 시작 @@@
'''

for _ in range(int(input())):
  # 입력받기
  R, C = map(int, input().split())
  board = []
  result = 0
  visited = [[False for _ in range(C)] for _ in range(R)]
  for _ in range(R):
    board.append(list(input()))
  
  # 코드 시작
  keys = parseKeys(list(input())) # 키 비트화
  openAllDoor(keys) # 일단 열 수 있는 문들 다 연다.
  q = deque(getEnter(board, visited))
  while q: # 탐색 시작
    now_r, now_c = q.popleft()
    now = board[now_r][now_c]
    if now.isupper(): # 문 인 경우
      if not canOpen(keys, now): # 못여는 문이면 지나침
        continue
    elif now.islower(): # 열쇠 획득한 경우
      if isNewKey(keys, now): # 새로운 키다 ? => 모든 문 다시 열고 visited 초기화한다.
        keys = addKey(keys, now)
        board[now_r][now_c] = '.'
        openAllDoor(keys)
        visited = [[False for _ in range(C)] for _ in range(R)]
        q = deque(getEnter(board, visited))
    elif now == "*":
      continue
    elif now == "$":
      result +=1
      board[now_r][now_c] = "." 
      
    for _r, _c in dir:
      nxt_r, nxt_c = now_r+_r, now_c+_c
      if not (0<=nxt_r<R) or not (0<=nxt_c<C):
        continue
      if board[nxt_r][nxt_c] == '*' or visited[nxt_r][nxt_c]:
        continue
      visited[nxt_r][nxt_c] = True
      q.append((nxt_r,nxt_c))
  # 출력
  print(result)
  # printBoard(board)

---

풀이)

BFS 와 비트마스킹을 이용한 탐색문제입니다.

하지만 조건이 많은 편이라 다른 BFS 문제들에 비해 구현이 까다로웠던 문제입니다.

따라서, 기능을 담당하는 함수들로 분리해서 구현했습니다!

 

열쇠 관련 주요 로직

현재 가지고 있는 열쇠 목록을 비트 형태인 keys 에 저장합니다. keys 26비트 형태 정수로 되어있으며, 각 자리가 0 이면 열쇠가 없음, 1이면 열쇠가 있음 을 의미합니다.

 

예) keys = b100000000000000000000000101 이면, A와 C 문을 열 수 있는 a, c 열쇠가 있음을 의미합니다.

이 방식을 비트마스킹이라고 하며, 이 방식을 이용해

'해당 문을 열수 있음을 판별하는 함수'

'키를 추가해주는 함수'

'모든 문을 여는 함수'

등을 만들어줍니다.

 

탐색할 때 주요 로직

0. 문은 탐색을 시작하기전에 현재 가지고 있는 키로 한번에 다 열어버린다.

1. 문을 마주친 경우 :

   -  못 연다면, 넘어간다. ( 사실 0번 케이스 땜에 여는지 못여는지 테스트 안해도 다 못여는 문일 듯 합니다😀)

2. 열쇠를 마주친 경우 :

   -  현재 가지고 있는 열쇠 목록을 업데이트, 열 수 있는 문들을 다시 모두 연다.

   -  탐색 큐와, visited 배열을 초기화 한 후, 다시 enter 가능한 곳 들을 q에 집어넣어준다.  

 

 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.