백준1194 - 달이 차오른다, 가자. (비트마스킹 & BFS) Python

https://www.acmicpc.net/problem/1194

 

해당 문제는 '0'에서부터 '1'로 향하되, 특정 소문자 알파벳인 열쇠를 지나쳐야 대문자 알파벳인 문을 통과할 수 있는 제약이 주어진 문제다.

따라서 길찾기에서는 BFS 알고리즘 로직을,  보유 열쇠 저장은 비트마스킹을 사용해야 메모리를 최대한 적게 사용하며 해당 풀이를 구현할 수 있다.

 

풀이 과정은 다음과 같다.

1. 입력값을 받아온 뒤, 이를 2차원 배열 크기인 n, m과 2차원 배열 matrix로 구분하고 시작점인 '0'의 좌표를 찾는다.

def solution (data) :
  n,m = map(int, data.pop(0).split())
  matrix = list(map(lambda x : list(x), data))
  
  x,y = None,None
  for i in range(n) :
    for j in range(m) :
      if matrix[i][j] == '0' :
        x,y = j,i
  
  result = BFS(matrix,x,y)
  print(result)

 

2. BFS 알고리즘을 구현한다.

이때, 열쇠 보유 현황은 비트마스킹을 활용하여 다음과 같이 구현했다.

아무 열쇠도 보유하지 않은 경우는 0이며, c를 가진 경우라면 4(100)로, a와 c를 가진 경우라면 5(101)로 저장할 수 있도록 했다. 

즉, 3차원 배열을 활용하여 열쇠 유무를 저장하는 것보다 더 적은 메모리로 구현이 가능하다.

def BFS(matrix,x,y):
  X, Y = len(matrix[0]), len(matrix)
  # visited 는 좌표에 따른 방문 여부 & 열쇠 보유 현황을 가진 2차원 배열
  visited = [[0 for _ in range(X)] for _ in range(Y)]
  d_keys = 0
  visited[y][x] = d_keys
  # 순서대로 x좌표, y좌표, 거리, 현재 열쇠 현황
  queue = deque([[x, y, 0, d_keys]])

  while queue:
    x, y, dist, keys = queue.popleft()
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    for dx, dy in directions:
      nx, ny = dx + x, dy + y
      # 유효 좌표가 아니거나 벽인 경우 패스
      if not locationVerify(nx, ny, X, Y) or matrix[ny][nx] == '#':
        continue
      
      # 열쇠를 습득한 경우, 열쇠 보유 현황이 변경되므로 선언한 변수
      temp_key = keys

      # 도착점이라면 리턴
      if matrix[ny][nx] == '1': return dist + 1
      
      # 대문자인 경우 (열쇠 보유 여부에 따라 진행 여부 결정)
      elif 'A' <= matrix[ny][nx] <= 'Z':
        # 새로 얻은 열쇠와 열쇠 중 가장 값이 낮은 'A' charCode의 차를 구한 뒤
        verify_key = ord(matrix[ny][nx]) - ord('A')
        # 지금 가지고 있는 열쇠들과 비교하여 가지고 있지 않은 경우 패스
        # 만약 내가 가진 열쇠가 5(a,c 보유)라하더라도, 새로 얻은 열쇠가 2(b)이라면
        # 5(101) & 2(10) == False 이므로 패스되는 것
        if not temp_key & (1 << verify_key) : continue
       
      # 소문자인 경우 (열쇠 획득)
      elif 'a' <= matrix[ny][nx] <= 'z':
        # 새로 얻은 열쇠를 키 현황에 추가
        key = ord(matrix[ny][nx]) - ord('a')
        temp_key |= (1 << key) 

      # 중복 이동 방지 조건문
      # 저번에 이동했을 때 열쇠 현황과 지금 열쇠 현황이 같다면 패스
      if visited[ny][nx] & (1 << temp_key): continue
      
      # 모든 조건문을 통과한 경우 열쇠 현황 업데이트 및 큐에 데이터 삽입
      visited[ny][nx] |= (1 << temp_key)
      queue.append([nx, ny, dist + 1, temp_key])

  return -1

def locationVerify (x,y,X,Y) :
  return 0 <= x < X and 0 <= y < Y

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
from collections import deque

def solution (data) :
  n,m = map(int, data.pop(0).split())
  matrix = list(map(lambda x : list(x), data))
  
  x,y = None,None
  for i in range(n) :
    for j in range(m) :
      if matrix[i][j] == '0' :
        x,y = j,i
  
  result = BFS(matrix,x,y)
  print(result)

def BFS(matrix,x,y):
  X, Y = len(matrix[0]), len(matrix)
  visited = [[0 for _ in range(X)] for _ in range(Y)]
  d_keys = 0
  visited[y][x] = d_keys
  queue = deque([[x, y, 0, d_keys]])

  while queue:
    x, y, dist, keys = queue.popleft()
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    for dx, dy in directions:
      nx, ny = dx + x, dy + y
      if not locationVerify(nx, ny, X, Y) or matrix[ny][nx] == '#':
        continue

      temp_key = keys

      if matrix[ny][nx] == '1': return dist + 1
      
      elif 'A' <= matrix[ny][nx] <= 'Z':
        verify_key = ord(matrix[ny][nx]) - ord('A')
        if not temp_key & (1 << verify_key) : continue
        
      elif 'a' <= matrix[ny][nx] <= 'z':
        key = ord(matrix[ny][nx]) - ord('a')
        temp_key |= (1 << key) 

      if visited[ny][nx] & (1 << temp_key): continue
      visited[ny][nx] |= (1 << temp_key)
      queue.append([nx, ny, dist + 1, temp_key])

  return -1

def locationVerify (x,y,X,Y) :
  return 0 <= x < X and 0 <= y < Y
  
solution(input_data)