BOJ 백준 파이썬 14940 공주님을 구해라!

삼차원 배열을 이용하는 전형적인 문제다.

아주 쉬운 문제

 

그램(2)을 발견하기전에는 z=0 이고 z가 0이면 벽을 못 뚫고

z=1이면 벽을 뚫을 수 있게 된다.

dist[z][x][y]에서 z의 범위는 0에서 1까지

z가 0일 때는 그람 없이 x,y좌표에 도달하는 최소 거리

z가 1일 때는 그람을 발견하고 난 후  x,y 좌표에 도달하는 최소 거리

 

 

import sys
from collections import deque
from itertools import combinations
 
 
### 3차원 배열 dist[gram][x][y] 생성 한다. gram=0-> 검 미발견(벽 못 뚫음)(gram[0][x][y]-> 검을 발견하지 못했을 떄 x,y좌표에 도달하는 최소 시간 1-> 검 발견(벽 뚫을 수 있음)
###                     
if __name__=='__main__':
    #sys.stdin=open("input.txt", "rt")
    
    n,m,t=map(int,input().split())  ##n=행,m=열,t=제한 시간
 
    board=[list(map(int,input().split())) for _ in range(n)]
 
    dist=[ [[-1]*m for _ in range(n)] for _ in range(2)]
 
    q=deque()
 
    q.append((0,0,0))
    dist[0][0][0]=0
 
    dx=[0,0,-1,1]
    dy=[1,-1,0,0]
    while q:
       z,x,y=q.popleft() ##검 발견 미발견,x좌표,y좌표
 
       for k in range(4):
           nx=x+dx[k]
           ny=y+dy[k]
 
           if 0<=nx<n and 0<=ny<m:
               if z==0: ## 벽을 못 뚫음
                       if board[nx][ny]==0: #빈 벽일시
                           if dist[z][nx][ny]==-1:
                               dist[z][nx][ny]=dist[z][x][y]+1
                               q.append((z,nx,ny))
                       elif board[nx][ny]==2: #그램일 시
                           if dist[z+1][nx][ny]==-1:
                            dist[z+1][nx][ny]=dist[z][x][y]+1
                            q.append((z+1,nx,ny))
               else: ##벽을 뚫을 수 있음
                    if dist[z][nx][ny]==-1:
                        dist[z][nx][ny]=dist[z][x][y]+1
                        q.append((z,nx,ny))
    min_time=float('inf')
    for z in range(2):
        if dist[z][n-1][m-1]!=-1:
            min_time=min(dist[z][n-1][m-1],min_time)
 
    if min_time<=t:
        print(min_time)
    elif min_time>t :
        print('Fail')