[파이썬] 백준 16954 : 움직이는 미로탈출 (골드3)

[파이썬] 백준 16954 : 움직이는 미로탈출 (골드3)

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

---

문제

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

---

풀이

0. 방향성 생각

• 맵이 시시각각 변하니 2차원 그래프로는 풀기 까다롭다.
• 1초 후의 상황들을 다음 층이라고 생각하고 3차원 array를 만든다.
• 이동 가능한 경우는, 가고싶은 위치에 현재 층이 #이 아닌 경우 and 가고싶은 위치의 다음 층에 #이 내려오지 않는 경우이다.
• 간선이 모두 동일하고 탈출 유무만 물어보므로 BFS로 풀이.

1. 입력

from collections import deque

temp = [list(input()) for _ in range(8)]
maze = [temp]

for _ in range(7):
    new_temp = [row[:] for row in temp]
    new_temp.pop()
    new_temp.insert(0,['.']*8)
    maze.append(new_temp)
    temp = new_temp

for _ in range(16):
    maze.append([['.']*8 for _ in range(8)])

• 시작 후 7초 동안은 #이 내려올 수 있다.
• 7초 후 위치에서 다시 도착지점까지 도달해야 하므로 16개를 더 추가해준다.
• 7초 후 왼쪽 아래에서 출발하는 worst case도 있으므로 16개 (사실은 가로 세로 7칸이면 14칸이라 충분하다)
  

2. BFS

dire = [(j,i,1) for j in (-1,0,1) for i in (-1,0,1)]
visit = [[[False]*8 for _ in range(8)] for _ in range(24)]
visit[0][7][0] = True
escape = 0
q = deque([(0,7,0)])
while q:
    x,y,z = q.popleft()

    if (x,y) == (7,0):
        escape = 1
        break

    for dx,dy,dz in dire:
        nx,ny,nz = x+dx,y+dy,z+dz
        if (0<=nx<8 and 0<=ny<8 and 0<=nz<24) and not visit[nz][ny][nx]:
            if maze[z][ny][nx] == '.' and maze[nz][ny][nx] == '.':
                visit[nz][ny][nx] = True
                q.append((nx,ny,nz))

print(escape)

• 어느 층이든 상관 없이 (7,0)에 도달하면 탈출 가능
• maze[z][ny][nx] == '.' : 가려는 곳에 #이 아니고
• maze[nz][ny][nx] == '.' : 다음 층에 #이 밀려오는 케이스가 아니면
• visit 체크하고 큐에 추가하기
  

---

전체코드

from collections import deque

temp = [list(input()) for _ in range(8)]
maze = [temp]

for _ in range(7):
    new_temp = [row[:] for row in temp]
    new_temp.pop()
    new_temp.insert(0,['.']*8)
    maze.append(new_temp)
    temp = new_temp

for _ in range(16):
    maze.append([['.']*8 for _ in range(8)])

dire = [(j,i,1) for j in (-1,0,1) for i in (-1,0,1)]
visit = [[[False]*8 for _ in range(8)] for _ in range(24)]
visit[0][7][0] = True
escape = 0
q = deque([(0,7,0)])
while q:
    x,y,z = q.popleft()

    if (x,y) == (7,0):
        escape = 1
        break

    for dx,dy,dz in dire:
        nx,ny,nz = x+dx,y+dy,z+dz
        if (0<=nx<8 and 0<=ny<8 and 0<=nz<24) and not visit[nz][ny][nx]:
            if maze[z][ny][nx] == '.' and maze[nz][ny][nx] == '.':
                visit[nz][ny][nx] = True
                q.append((nx,ny,nz))

print(escape)

코멘트

• 기본 BFS