[Python][백준 1194][BFS][bit masking] 달이 차오른다, 가자. - 컴도리돌이

반응형

---

풀이과정

해당 문제는 방문 표시만 제대로 하면 쉽게 해결할 수 있는 문제이다.

물론 방문 표시가 생각보다 까다롭다.

😂

 

시작점에서 끝점까지 도달하는 최단 거리는 너비 우선 탐색(BFS)으로 구현하면 된다.

그렇다면 이 문제의 핵심은 방문 표시이다.

탈출을 하기 위해서는 '.' 공간만 이용할 수 있다.

물론 주어진 n*m 행렬 맵에서는 키라는 특이한 요소를 첨가했다.

키의 종류는 a, b, c, d, e, f 총 6가지이며,

키의 종류 따른 문의 종류도 A, B, C, D, E, F 총 6가지이다.

 

문제에서는 탈출구까지 가는 길에 문이 있으면

해당 문에 맞는 키 값을 소유하고 있어야 한다.

 

그렇기 때문에 BFS 탐색할 때 

방문 표시를 가지고 있는 키 값들에 따라 해주어야 한다.

키의 종류는 총 6가지이다.

그렇기 때문에 방문 표시도 2^6 = 64개만큼 생성해주면 된다.

 

1. '0'부터 BFS 탐색을 시작한다.

 

2. 새롭게 이동한 곳이 '1' 이거나 '.'이면

해당 키 값에 따른 방문 표시를 해주고

q에 이동 좌표를 삽입해준다.

 

3. 새롭게 이동한 곳이 'abcdef'에  key가 존재하는 경우,

현재 key에서 or 연산을 통해 key를 획득하고

q에 업데이트 키와 함께 삽입해준다.

 

4. 새롭게 이동한 곳이 "ABCDEF"에 key가 존재하는 경우,

현재 key에 and 연산을 통해 문을 통과할 수 있는지 확인해준다.

 

5. '1'에 도달할 경우 cnt를 리턴, 도달하지 못할 경우 while문 종료 및 -1 리턴

---

풀이 코드

from collections import deque

def bfs() :
 start = None
 for i in range(n) :
   if start != None : break
   for j in range(m) :
     if board[i][j] == "0" : 
       board[i][j] = '.'
       start = (i,j)
  x,y = start
  q = deque([(x,y,0,0)])
  visited = [[[0] * 64 for _ in range(m)] for _ in range(n)]
  dx,dy = [0,0,-1,1],[-1,1,0,0]
  visited[x][y][0] = True
  while q :
    x,y,cnt,key = q.popleft()
    if board[x][y] == "1" :
      return cnt
    else :
      for i in range(4) :
        nx,ny = x + dx[i],y + dy[i]
        if 0 <= nx < n and 0<= ny < m and board[nx][ny] != '#' and not visited[nx][ny][key] :
          if board[nx][ny] == '.' :
            visited[nx][ny][key] = True
            q.append((nx,ny,cnt+1,key))
          elif board[nx][ny] == "1" :
            return cnt+1
          elif board[nx][ny] in "ABCDEF" and key & 1 << (ord(board[nx][ny])- 65):
            visited[nx][ny][key] = True
            q.append((nx,ny,cnt+1,key))
          elif board[nx][ny] in "abcdef" and not visited[nx][ny][key|(1 << ord(board[nx][ny]) - 97)] :
            visited[nx][ny][key | (1 << ord(board[nx][ny]) - 97)] = True
            q.append((nx,ny,cnt+1,key | (1 << ord(board[nx][ny]) - 97)))
  return -1
n,m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]
print(bfs())