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

0. 문제 링크

 

 

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

16954번: 움직이는 미로 탈출

---

1. 풀이 방법

 

 

첫 번째로는 어떤 생각이 들었냐면, 내가 한 칸 올라가고 벽이 한 칸 내려오니까 사실상 내가 두 칸 올라가는 것은 아닐까?

라는 생각이 들었다. 

근데 그건 귀찮을 것 같아서 그냥 넘겼고, 아무튼! 다른 생각을 했다.

이건 누구나 생각하겠지만, 내가 지금 가려는 곳이 벽이어서도 안 되고, 벽이 내려온 후에도 안전해야 한다.

사실 벽이 아래를 기준으로 한 칸 위에만 있다면, 그 라인만 넘어가면 무조건 도착지에 도착이 가능하다.

문제에서는 도착을 할 수 있냐, 없냐를 물어보고 있으므로, 최상단의 벽만 넘어가면 무조건 1을 출력하면 되는 것이다.

따라서 나는 최상단의 벽과 아래의 거리를 구했고, 그만큼 맵을 만들었다.

첫 번째 맵은 입력으로 받은 맵, 두 번째 맵은 첫 번째 맵에서 벽이 한 칸씩 내려간 것... 뭐 아무튼 이런 식으로 벽이 맵에서 없어질 때까지 맵을 만들었다.

암튼 이렇게 만들고 이번 맵과 다음 맵에서 조건을 충족하면, 다음 맵으로 넘어갔다.

그런 식으로 모든 맵에서 살아남으면 1을 출력하고 끝냈다.

참고로 따로 방문처리는 하지 않았다.

왜냐면 같은 곳을 왔다갔다하면서 피할 수도 있기 때문이다. (아마?)

---

2. 코드

 

 

from collections import deque

board = [[[b for b in input()] for _ in range(8)]]

rank = 8
for i in range(8):
    if '#' in board[0][i]:
        rank = i
        break

rank = 8 - rank
# 맨위에 있는 벽과 가장 아래까지 거리를 구함
# 따라서 해당 거리만큼만 벽이 내려가면 됨

for i in range(0, rank):        # 벽을 아래로 내려서 다른 board에 추가함
    new = [['.' for _ in range(8)] for _ in range(8)]
    for j in range(1, 8):
        new[j] = board[i][j - 1].copy()
    board.append(new)

dq = deque()
dq.append([0, 7, 0])

# 맨 위부터 시계 방향
dy = [-1, -1, -1, 0, 1, 1, 1, 0, 0]
dx = [-1, 0, 1, 1, 1, 0, -1, -1, 0]
        
while dq:
    i, y, x = dq.popleft()      # i는 board들의 인덱스
    for j in range(9):
        ny, nx = y + dy[j], x + dx[j]
        if i >= rank:       # i가 rank와 같거나 크다는 뜻은 벽이 다 내려가도 살았다는 뜻임
            print(1)
            exit(0)
        elif 0 <= ny < 8 and 0 <= nx < 8 and board[i][ny][nx] != '#' and board[i + 1][ny][nx] != '#':
            # 이동할 위치가 현재 보드에서 벽이 아니어야 하고, 다음 보드에서도 벽이 아니어야 함
            dq.append([i + 1, ny, nx])      # 살았으므로 다음 board로 넘어감
print(0)

---

3. 마무리

 

 

무난무난