[백준 16954] 움직이는 미로 탈출(Python)

오랜만에 알고리즘 공부해서 그런지, 구현이 너무 힘들었다

1. 요약

움직이는 미로에서 사람이 탈출 가능한지 묻는 문제

구체적으로 설명하면, 사람이 이동한다.(대각선 방향으로 인접한 곳으로 1칸이동, 상하좌우 인접한 방향으로 1칸 이동, 제자리) 그 다음, 벽이 아래 행 방향(↓ 방향)으로 이동한다. 만약 벽이 이동한 곳에 사람이 있다면 탈출 불가능이라고 한다. 가장 왼쪽 아랫칸에 시작하여 가장 오른측 윗칸에 도착해야 탈출 성공이다.

2. 아이디어

BFS로 해결한다. queue에 들어갈 아이템은 사람의 위치, (y, x) 현재 벽들의 위치에 대한 list이다. (메모리 측면에서 비효율적임)

사람이 다음 위치로 이동할 때, 위에서 언급된 list를 이용하여 벽의 위치와 나의 위치를 고려하여 이동한다. 다시 말해, 다음 위치에 벽이 있으면 안되고, 다음 위치 바로 위에 벽이 있으면 안된다.

사람이 움직이지 않고 제자리에 있는 경우도 처리해야하는데, 내가 작성한 코드의 경우, 방문 여부를 나타내는 visited 변수가 방문 위치만 고려하는 2차원 배열이기 때문에, 현재 벽들의 위치에 대한 list가 있을 경우에만 queue에 넣었다.

3. 코드

import sys
from collections import deque

n = 8
walls = []
arr = []
d = ((0,1), (0,0), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1))

for i in range(n):
    line = list(sys.stdin.readline().rstrip())
    for j in range(n):
        if line[j] == '#': walls.append((i,j))

arr = [['.' for _ in range(n)] for _ in range(n)]

def isin(y, x):
    if -1<y<n and -1<x<n: return True
    return False

def get_moved_walls(current_walls):
    new_walls = []
    for y, x in current_walls:
        if isin(y+1, x): new_walls.append((y+1, x))

    return new_walls

def solve():
    q = deque()
    q.append((n-1, 0, walls))
    visited = [[False for _ in range(n)] for _ in range(n)]
    visited[n-1][0] = True
    
    while q:
        y, x, current_walls = q.popleft()
     
        if (y, x) == (0, n-1): return 1

        for i in range(9):
            ny = y + d[i][0]
            nx = x + d[i][1]

            if isin(ny, nx):
                if (ny, nx) in current_walls: continue
              
                flag = True
                for wy, wx in current_walls:
                    if (wy, wx) == (ny-1, nx):
                        flag = False
                        break
                    
                if not flag: continue

                if not visited[ny][nx] or ((ny, nx) == (y, x) and current_walls):
                    visited[ny][nx] = True
                    new_walls = get_moved_walls(current_walls)
                    q.append((ny, nx, new_walls))

    return 0

print(solve())