BOJ 백준 파이썬 16954 움직이는 미로 탈출

풀이법은 2가지가 있다.

 

1)첫 번째는 8x8배열이니까 어차피 8초가 지나면 모든 벽이 사라지니까

0초~8초(8초 이후는 무의미하니 8초로 고정) 일때의 삼차원 배열을 선언해서 풀이하는 방법

하지만, 이 방법은 어렵고 헷갈려서 시험장에서 자연스럽게 떠올리기 힘들 것 같다는 생각에

내 스타일은 아니라고 판단하였다.

t초후의 벽은 board[nx-t][ny]라는 발상도 멋지지만 막상 떠올릴 수 있을까? 생각

bfs 조건도 낯설었다.

 

import sys
from collections import deque
 
if __name__=='__main__':
   # sys.stdin=open("input.txt", "rt")
    board=[list(map(str,input())) for _ in range(8)] ##8x8 행렬 받기
 
    dQ=deque()
 
    dQ.append((0,7,0)) ##욱제는 0초에 (7,0)에서 시작
    visit=[[[0]*8 for _ in range(8)] for _ in range(0,9)] ## visit[time][x][y] time일때의 x,y좌표를 방문 했는지 0=방문 안 함, 1=방문 함
    dx=[1,0,-1,0,1,1,-1,-1,0] ##9방향으로 이동 가능
    dy=[0,1,0,-1,-1,1,1,-1,0] 
    visit[0][7][0]=1
    ok=0
    while dQ:
      
            now=dQ.popleft()
            t=now[0] # 시각
            x=now[1]
            y=now[2]
            tt=min(t+1,8)
            
 
            if x==0 and y==7:
                ok=1
            for i in range(9):
                xx=x+dx[i]
                yy=y+dy[i]
                tt=min(t+1,8)
                if 0<=xx<8 and 0<=yy<8:
                    if xx-t>=0 and board[xx-t][yy]=='#':
                        continue
                    if xx-t-1>=0 and board[xx-t-1][yy]=='#':
                        continue
 
                    if visit[tt][xx][yy]==0:
                        visit[tt][xx][yy]=1
                        dQ.append((tt,xx,yy))
 
    if ok==1:
        print(1)
    else:
        print(0)

 

 

 

 

2)두 번째는 1초가 흐를때마다 맨 아래 줄은 pop으로 없애고 '.'로만 이루어진 리스트를 첫번째 원소에 삽입하고

visit배열을 초기화시켜준다. 왜냐? 시간이 흐를때마다 리스트의 원소는 바뀌니까

그렇게하여 bfs를 진행하는 방식

두 번째 방식이 가장 무난하고 정통적인 방식이라 생각한다.

내가 충분히 소화 가능하고 자연스럽게 떠올릴 수 있는 발상 

다른 조건 따지는 것들은 쉬우니 설명 생략

impimport sys
from collections import deque
from itertools import combinations
 
 
if __name__=='__main__':
    #sys.stdin=open("input2.txt", "rt")
    
    board=[list(map(str,input())) for _ in range(8)]
 
    dx=[0,0,0,-1,1,-1,-1,1,1]
    dy=[0,1,-1,0,0,-1,1,1,-1]
 
 
    
    q=deque()
    q.append((7,0)) ##(x좌표,y좌표)
    t=['.']*8
 
    while q:
 
        for _ in range(len(q)):
            visit=[[-1]*8 for _ in range(8)]  
            x,y=q.popleft()
 
            if x==0:
                print(1)
                exit()
            for k in range(9):
                nx=x+dx[k]
                ny=y+dy[k]
                if 0<=nx<8 and 0<=ny<8:
                    if board[nx][ny]!='#': 
                        if board[nx-1][ny]!='#':
                            #print(nx,ny)
                            if visit[nx][ny]==-1:
                                visit[nx][ny]=1
                                q.append((nx,ny))
        s=board.pop()
        board.insert(0,t)
    print(0)