[BOJ/Python] 16954: 움직이는 미로 탈출

gold 3 / boj-16954: 움직이는 미로 탈출

문제 흐름

2가지 함수를 통해 구현했다.

🎾 move_walls

grid를 입력받아 벽을 한칸씩 아래로 밀어 변환하는 함수다.

🎾 move_charactere

grid와 q를 입력받아 현재 들어있는 큐에 대해서 아래의 작업을 한 뒤,
다음 반복문 실행 여부 플래그인 next와 다음 q에 들어갈 리스트인 next_q를 반환한다.

1. 현재 위치가 이전 단계에서 이동한 벽과 부딪친 위치인지 확인하고, 부딪쳤다면 continue한다.
2. 만약 목적지인 (0, 7)에 도착했다면, False와 빈 리스트를 반환한다.
3. 현재 위치에서 9방향(제자리를 포함)으로 이동한 위치에 대해
   체스판을 벗어나지 않고,
   벽이 아니고,
   이미 next_q에 들어갔는지 여부를 체크하는 visited에 없다면
   next_q에 추가하고, visited에도 추가한다.

모든 q의 원소에 대해 작업을 완료했다면 move_walls를 통해 벽을 움직인 뒤,
True와 next_q를 리턴한다.

move_character함수는 처음 출발지인 (7, 0)을 초기값으로 세팅한 next_q와 q, True값을 가진 next를 시작으로 while문을 통해 탐색을 수행한다.

while문은 next가 False이거나 next_q가 빈 리스트일 경우 중단한다.
지금 보니 next_q가 빈 리스트일 경우 중단한다는 조건으로 바꿔도 충분할듯하다.

탐색을 종료했을 때, next가 True라면 중간에 멈춘 것이므로 도착할 수 없다 "0"을 출력하고,
False라면 도착한 것이므로 "1"을 출력한다.

코드

# 우ㅁ직이는 미로 탈출
# BFS

import sys
from collections import deque
input = sys.stdin.readline

dx = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 0, 1, -1, 0, 1]

def move_walls(grid):
    row = [(-1, ".") for _ in range(8)]
    for i in range(8):
        for j, row_info in enumerate(row):
            r, w = row_info
            row[j] = (r+1, grid[i][j])
            grid[i][j] = w
    # print(*grid, sep="\n")

def move_character(grid, q):
    # print(*grid, sep="\n")
    next_q = []
    visited = set()
    while q:
        x, y = q.popleft()
        if grid[x][y] == "#":
            # print("벽과 부딪침")
            continue
        if (x, y) == (0, 7):
            # print("도착")
            return False, []
        for d in range(9):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < 8 and 0 <= ny < 8:
                if grid[nx][ny] == "#":
                    # print("벽이라 갈 수 없음")
                    continue
                if (nx, ny) in visited:
                    # print("이미 방문하기로한 칸")
                    continue
                next_q.append((nx, ny))
                visited.add((nx, ny))
                # print("방문 완료")
    move_walls(grid)
    # print(next_q)
    return True, next_q

if __name__ == "__main__":
    grid = [list(input().rstrip()) for _ in range(8)]
    x, y = 7, 0 #from / to = 0, 7
    
    next = True
    next_q = (x, y)
    q = deque([next_q])
    
    while next and next_q:
        next, next_q = move_character(grid, q)
        q.extend(next_q)
    if next:
        print(0)
    else:
        print(1)