[파이썬] 백준 1473 : 미로 탈출 (플레5)

[파이썬] 백준 1473 : 미로 탈출 (플레5)

• https://www.acmicpc.net/problem/1473

 

---

풀이

방향성 생각

• 작은 맵 + state가 변하는 2 요소 = 비트필드를 이용한 BFS
  • 카카오 기출에서 비슷한 문제가 있었다.
• 현재 맵 상태를 bit로 나타내고 큐에 같이 넣어주기.
• 가로로 이동하는 경우
  1. 현재 칸이 가로로 이동가능 (A or 회전안된D or 회전된 C)
  2. 다음 칸이 가로로 이동가능 (A or 회전안된D or 회전된 C)
  3. 다음 칸이 가로로 이동 불가능 (회전된D or 회전안된C)
• 세로로 이동하는 경우도 마찬가지이다.
  • 현재에서 원하는 방향으로 나갈 수 있는지 체크
  • 다음 칸이 회전 안하고 갈 수 있는지 체크 (상태 s 그대로)
  • 다음 칸을 회전하고 가야 하는지 체크 (상태 ns로 변경 후 제자리에 큐 추가)

---

전체코드

from collections import deque, defaultdict as dd

inside = lambda x,y : 0<=x<W and 0<=y<H
dire = [(1,0),(0,1),(-1,0),(0,-1)]

def toggle(x,y,s):
    ns = s
    for j in range(y*W,y*W+W): # 행 토글
        ns ^= (1<<j)
    for i in range(x,W*H,W): # 열 토글
        ns ^= (1<<i)
    return ns

def update(x,y,s,t):
    global V,G
    if V[(x,y,s)] == -1:
        V[(x,y,s)] = t+1
        Q.append((x,y,s,t+1))

H,W = map(int,input().split())
arr = [input() for _ in range(H)]

V = dd(lambda : -1)
V[(0,0,0)] = 0  # x y s -> t
Q = deque([(0,0,0,0)])
answer = -1
while Q:
    x,y,s,t = Q.popleft()

    if (x,y) == (W-1,H-1):
        answer = t
        break

    for idx,(dx,dy) in enumerate(dire):
        nx,ny = x+dx,y+dy
        is_ver = idx%2
        ns = toggle(x,y,s)
        if inside(nx,ny) and arr[ny][nx] != 'B':

            # 세로이동
            if is_ver and (arr[y][x] == 'A' or (arr[y][x] == 'C' and not s&(1<<(x+y*W))) or (arr[y][x] == 'D' and s&(1<<(x+y*W)))):

                # 제자리에서 회전
                update(x,y,ns,t)

                # 회전 x : 다음 A or 회전안된 C or 회전된 D
                if (arr[ny][nx] == 'A') or (arr[ny][nx] == 'C' and not s&(1<<(nx+ny*W))) or (arr[ny][nx] == 'D' and s&(1<<(nx+ny*W))):
                    update(nx,ny,s,t)
                # 회전 : 회전안된D or 회전된 C 회전하면서
                elif (arr[ny][nx] == 'D' and not ns&(1<<(nx+ny*W))) or (arr[ny][nx] == 'C' and ns&(1<<(nx+ny*W))):
                    update(nx,ny,ns,t)

            # 가로이동
            elif not is_ver and (arr[y][x] == 'A' or (arr[y][x] == 'C' and s&(1<<(x+y*W))) or (arr[y][x] == 'D' and not s&(1<<(x+y*W)))):
                # 회전 x : 다음 A or 회전안된D or 회전된C
                update(x,y,ns,t) # 제자리에서 회전
                if (arr[ny][nx] == 'A') or (arr[ny][nx] == 'D' and not s&(1<<(nx+ny*W))) or (arr[ny][nx] == 'C' and s&(1<<(nx+ny*W))):
                    update(nx,ny,s,t) # 회전 안하고 다음칸
                # 회전 : 회전안된 C or 회전된 D 회전하면서
                elif (arr[ny][nx] == 'C' and not ns&(1<<(nx+ny*W))) or (arr[ny][nx] == 'D' and ns&(1<<(nx+ny*W))):
                    update(nx,ny,ns,t)

print(answer)

 

---

코멘트

• 함수로 코드 줄이다가 오타나서 한참 찾았...
• 조건문의 경우도 간단하게 함수 써서 딕셔너리로 매핑하는게 필요할듯.