[백준16954번] 움직이는 미로 탈출(파이썬)

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

16954번: 움직이는 미로 탈출

이 문제는 쉬운 bfs문제처럼 보이지만

'벽이 움직인다'라는 까다로운 조건이 붙어서

애를 많이 먹었습니다.

저는 처음에

while wall:
    wx,wy=wall.pop(0)
    nwx=wx+1
    if nwx>=8:
        continue

    else:
        if [nwx,wy] in man:
            p=man.index([nwx,wy])
            man.pop(p)
        room[nwx][wy]='#'
        new_wall.append([nwx,wy])
    room[wx][wy]='.'
wall=new_wall

이렇게 벽을 이동시켜도보고

for x in range(7,-1,-1):
    for y in range(8):
        if room[x][y]=='#':
            if x==7:
                room[x][y]='.'
            else:
                room[x+1][y]='#'
                room[x][y]='.'
                if [x+1,y] in man:
                    p=man.index([x+1,y])
                    man.pop(p)

 

이렇게도 벽을 이동시켜봤지만...

어디선가 뭔가 계속 꼬였습니다.

결국 구글링을 하다가 알아낸 건

지도를 받을 때 deque로 받은 후,

마지막 줄을 pop를 한 후,

새로운 줄을 계속 더해주는 방식이었습니다.

그럼 맨 아래로 간 벽은 사라지는 식이었죠.

#백준 16954 움직이는 미로 탈출
from collections import deque


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

room=deque(list(input())for _ in range(8))

man=deque()
man.append([7,0])
new=['.','.','.','.','.','.','.','.']


turn=0
out=False
while man:
    len_man=len(man)
    for _ in range(len_man):
        x,y=man.popleft()
        if x==0 and y==7:
            out=True
            break
        if room[x][y]=='#':
            continue

        for d in range(9):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=8 or ny<0 or ny>=8:
                continue

            if room[nx][ny]=='#':
                continue
            man.append([nx,ny])
    if out==True:
        break
    room.pop()
    room.appendleft(new)
    turn+=1
    if turn==9:
        out=True
        break
if out==True:
    print(1)
else:
    print(0)

 

https://data-flower.tistory.com/92

[백준 16954번] 움직이는 미로 탈출 - 파이썬

도움이 되었던 코드입니다.

 

https://ku-hug.tistory.com/151

[Python/파이썬] 백준 16954번: 움직이는 미로 탈출

이외에도

벽이 아래로 내려오는 걸 관점을 달리해서

'욱제가 한 칸 위로 움직인다'

라고 보고 해석한 코드도 있습니다.

이 방식을 보고 해석이 독특해서 

참신하다는 생각이 들었습니다.