백준 16954 움직이는 미로 탈출 python

 

문제로이동

16954번: 움직이는 미로 탈출

---

목차

 

---

---

시작하기 전에

2개월 전에 스터디에서 공통 문제로 풀었다가 실패했던 문제였습니다.

이번엔 노트에 로직을 정리하고 1WA를 맞은 뒤 이거다! 싶어서 수정했는데 정답이었고 2회에 걸쳐 로직을 수정/추가했습니다.

 

접근 방법

벽이 움직인다는 점에서 캐슬디펜스 문제와 비슷하다고 생각했습니다.

비슷한 방식으로 접근했다가 큰 코 다쳤는데 그 이유는 캐슬 디펜스에선 주인공 위치가 고정되어 있지만, 이번 문제는 사방탐색(상하좌우) 뿐만 아니라 대각선 이동까지 가능했기 때문입니다.

즉, 벽의 이동뿐만 아니라 주인공의 이동까지 고려해야 했습니다.

 

주인공 탈출 조건

먼저, 주인공의 탈출 조건에 대해 생각해봅시다.

우측상단까지 도달해야한다? 즉, y좌표가 0에 도달하기만 해도 성공합니다.

그 이유는 벽은 계속해서 내려올 것이고 한 번이라도 상단에 도착한다면 이미 모든 벽은 내려가고 없기 때문입니다.

    if cur[1]==0 or cur[2]==7:
        answer=1
        break        
    for dx,dy in direction:
        nx = cur[0]+dx
        ny = cur[1]+dy
        if 0>nx or 0>ny or MAX<=nx or MAX<=ny:continue
        if ny-cur[2]<0:
            dq.clear()
            answer=1
            break

 

처음 제가 생각했던 탈출 조건은 주인공의 y좌표가 0에 닿았거나 버틴 시간이 7턴이라면 탈출되게 하였습니다.

또한 방향탐색을 하는 반복문 안에서 next_y 좌표가 음수가 되는 순간(결국 0에 닿았다는 소리) 탈출되게 하였습니다.

하지만 이 로직은 중복되었기 때문에 이후에 수정합니다.

 

주인공 이동 방법

필드는 가만히 있고 상대적인 좌표로만 제어할 것이기 때문에 연산이 중요했습니다.

첫째, 주인공이 이동할 위치에 벽이 있는가?

둘째, 만약 그 위치로 이동한다면 다음에 벽에 부딪히는 것은 아닌가?(바로 위에 벽이 있는가?)

 

if field[ny-cur[2]][nx]=='#':continue        
if field[ny-(cur[2]+1)][nx]=='#':continue

 

여기서 cur[2]는 이동 횟수(턴)입니다. 1턴이 지날 때마다 Deque에는 이전 이동시간+1을 해줍니다. 주인공의 턴 횟수에 따라 벽의 움직임을 유동적으로 조절 할 수 있기 때문입니다.

 

첫번째 조건문은 내가 이동할 위치에 벽이 없는가? 이며,

두번째 조건문은 내가 이동할 위치 바로 위에 벽이 없는가? 입니다.

 

이런 방식으로 구현한다면 벽의 직접적인 이동 없이 좌표값만으로 탈출 할 수 있을것이라 확신했습니다.

 

로직 최종 수정

우선 처음 언급했었던 탈출조건 로직을 단순화했습니다.

if ny-cur[2]<0:
	dq.clear()
	answer=1
	break

 

그 다음으로 중복된 좌표가 Deque에 들어오기에 visited 처리를 해주었습니다.

if visited[ny][nx]>=cur[2]+1:
	continue
	#중간생략
visited[ny][nx]=cur[2]+1

 동일한 좌표로 이동했고, visited에 이동 시간을 기록하는데, 이 시간이 같거나 (현재 시점에서)작은 경우 같은 결과를 만들어 내기 때문에 continue 시켜주었습니다.

 

---

소스 코드

Python

from collections import deque
MAX = 8
direction = [[0,0],[0,-1],[0,1],[-1,0],[1,0],[-1,-1],[1,-1],[1,1],[-1,1]]
field=[list(input()) for _ in range(MAX)]
visited=[[0]*MAX for _ in range(MAX)]
dq = deque([[0,7,0]])
answer = 0
while dq:
    cur = dq.popleft()
    for dx,dy in direction:
        nx = cur[0]+dx
        ny = cur[1]+dy
        if 0>nx or 0>ny or MAX<=nx or MAX<=ny:continue
        if ny-cur[2]<0:
            dq.clear()
            answer=1
            break
        if visited[ny][nx]>=cur[2]+1:continue
        if field[ny-cur[2]][nx]=='#':continue        
        if field[ny-(cur[2]+1)][nx]=='#':continue        
        dq.append([nx,ny,cur[2]+1])
        visited[ny][nx]=cur[2]+1
print(answer)