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

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

16954번: 움직이는 미로 탈출

 

생각하기

시간이 1초씩 지남에 따라서 

1. 욱제가 이동하고

2. 벽이 바뀐다

 

시간이 1초씩 바뀌는 것을 단계별로 나타내기 위해서 bfs를 사용한다

 

구현하기

큐에다가 row, col 좌표, 흘러간 시간을 묶어서 append 시킨다

큐에서 popleft시키면서 흘러간 시간이 바뀐 경우 체스판의 벽을 한줄씩 내린다

 

주의할 점 1

체스판의 벽이 한줄씩 내려가다보면 가장 위쪽행은 모두 벽이 없는 상태가 된다

-> 맨 위행으로 가면 결국 목적지에 도달할 수 있다

 

주의할 점 2

이동 패턴 중에 가만히 있는 경우도 있다.

이때, visited가 문제가 된다 -> 이전에 visited 가 true 이므로 큐에 append하지 않게 된다 

-> 이 경우에는 visited가 true이더라도 시간을 증가시켜 큐에 append할 수 있도록 해야한다

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

chess = []
for i in range(8):
    chess.append(list(map(str, input().strip())))



#오위 오 오아 아 아왼 왼 왼위 위 
dy = [-1, 0, 1, 1, 1, 0, -1, -1, 0]
dx = [1, 1, 1, 0, -1, -1, -1, 0, 0]

visited = [[False]* 8 for r in range(8)]

def bfs():
    q = deque()
    q.append((7, 0, 0))
    time_save = 0
    visited[7][0] = True

    while q:
        y, x, time = q.popleft()

        if time > time_save:
            chess.pop()
            chess.insert(0, ['.', '.', '.', '.', '.', '.', '.', '.'])
            time_save = time
        
        if y==0:
            return 1
        
        for i in range(9):
            ny = y + dy[i]
            nx = x + dx[i]


            if 0<=ny<8 and 0<=nx<8 and chess[ny][nx] == '.':
                if i == 8:
                    q.append((ny, nx, time+1))
                elif chess[y][x] == '.':
                    visited[ny][nx] == True
                    q.append((ny, nx, time+1))
        
    return 0


print(bfs())

 

발전시키기 1

3608ms가 너무 오래 걸린거 같은 느낌이 들어서 개선하고자 했다

맨 위줄에 도착하면 가장 오른쪽 위에 갈 수 있는 것처럼

가장 오른쪽 줄에 도착하면 가장 오른쪽 위에 갈 수 있다 -> 결국에는 시간이 지나면서 내려올 것이기 때문

	if y==0 or x==7:
            return 1

 

발전시키기 2

여태까지는 하나씩 row들을 내려주고 앞에 insert해주었는데

백준 강의를 보면서 더 줄일 수 있는 방법을 찾았다.

• 8초후에는 모든 칸에서 벽이 없어진다
• 체스판은 가만히 납두고 다음 이동시의 칸에 벽이 있는지 time을 row에서 빼주어서 체크
• 체스판은 가만히 납두고 이동 후에 한 줄이 내려왔을 때, 벽이 있는지 time+1을 row에서 빼주어서 체크

물론 움직이지 않았을 때는 따로 빼주어서 예외로 처리해주어야

 

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

chess = []
for i in range(8):
    chess.append(list(map(str, input().strip())))



#오위 오 오아 아 아왼 왼 왼위 위 
dy = [-1, 0, 1, 1, 1, 0, -1, -1, 0]
dx = [1, 1, 1, 0, -1, -1, -1, 0, 0]

visited = [[False]* 8 for r in range(8)]

def bfs():
    q = deque()
    q.append((7, 0, 0))
    time_save = 0
    visited[7][0] = True

    while q:
        y, x, time = q.popleft()

        
        if y==0 or x==7:
            return 1
        
        for i in range(9):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0<=ny<8 and 0<=nx<8:
                if i == 8 :
                    if ny-time < 0 or time>=8:
                        q.append((ny, nx, time+1))
                    
                    elif chess[ny-(time+1)][nx] == '.' and chess[ny-time][nx] == '.' :
                        q.append((ny, nx, time+1))
            
                elif visited[ny][nx] is False:
                
                    if ny-time < 0 or time>=8 :
                        visited[ny][nx] = True
                        q.append((ny, nx, time+1))
                    elif chess[ny-time][nx] == '.' and chess[ny-(time+1)][nx] == '.':
                        visited[ny][nx] = True
                        q.append((ny, nx, time+1))

    return 0


print(bfs())