[Python/BOJ] 백준 14442 벽 부수고 이동하기2(BFS)-시간초과에서 삽질하다가 AC

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

14442번: 벽 부수고 이동하기 2

 

 

 

앞서 벽 부수고 이동하기 를 풀었기에 이 문제를 풀 아이디어는 쉽게 얻을 수 있었다.

 

💡 방법

 

vis 배열을 3차원으로 만드는 것이 아니라 입력되는 k에 따라서 차원을 만드는 것이다.

그후 k번 벽을 뚫을 수 있으므로 뚫을 때마다 -1 씩 줄어들도록 코드를 만들었다.

 

 

 

코드는 나와있는 테케의 정답대로 잘 나왔고 제출하였다.

 

 

그러나

 

계속해서 시간초과가 발생하였다.

 

 

어쩔수없이 카톡방에 물어보았고 

호석님이 답변을 해주셨다.

 

 

 

 

 

 

from collections import deque
q = deque()
from sys import stdin
input = stdin.readline

n,m,k = map(int, input().split())
vis = [[[0]*(k+1) for _ in range(m)] for __ in range(n)]
arr = [list(map(int,input().strip())) for _ in range(n)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]

def bfs() :
    q.append([0,0,k]) # k는 벽을 뚫을 수 있는 수
    vis[0][0][k] = 1
    while q :
        x,y,z = q.popleft()
        if x == n-1 and y == m-1 :
            return vis[x][y][z]
        for i in range(4) :
            nx ,ny = dx[i] + x, dy[i]+y
            if 0<=nx<n and 0<=ny<m :
                if arr[nx][ny]==1 and z>0 and vis[nx][ny][z-1]==0:
                    vis[nx][ny][z-1] = vis[x][y][z]+1
                    q.append([nx,ny,z-1])
                elif arr[nx][ny]==0 and vis[nx][ny][z]==0:
                    vis[nx][ny][z] = vis[x][y][z]+1
                    q.append([nx,ny,z]) 
    return -1

print(bfs())

 

 

 

벽을 뚫을 때 arr[nx][ny]==1 and z>0 and vis[nx][ny][z-1] ==0 : 이 줄 에서

vis[nx][ny][z-1]==0 을 포함시키지않았었다.

내가 벽을 뚫고 갈 곳을 가봤었는지 확인하지 않아서 시간초과가 발생하였나보다.

벽 부수고 이동하기 1은 한번만 벽을 부수면 끝이라서 생각해주지않았던 부분이다.

 

 

 

앞으로는 이런 부분도 자세하게 생각하며 코드를 만들자!