[Python] 백준 14442 벽 부수고 이동하기2

문제 보러 가기

이전에 벽 부수고 이동하기를 풀어서 대부분의 로직은 똑같았다.

💡 포인트

앞서 이전에 푼 벽 부수고 이동하기는 벽을 딱 한번 부실수 있었는데, 이 문제는 k번 부실수 있어 3차원 배열을 만드는 것이 아니라 입력되는 k에 따라 차원을 만들면 된다.

그후 k번 벽을 뚫을 수 있으므로 뚫을 때마다 +1 씩 줄어들도록 코드를 만들었지만, 계속 시간초과가 났다,,,

시간 초과 해결 방법

일단 찾아보니 이 문제를 python으로 푸신 분은 시간초과를 통과하신분은 못봤다... pypy3로 바꿔서 했지만 계속 시간 초과가 났는데

해당 시간 초과에 영향을 많이 끼친 코드

      if xx<0 or xx>=n or yy < 0 or yy>=m:
                continue
            if a[xx][yy] == 1 and c < k and visit[xx][yy][c]==0:
                visit[xx][yy][c+1] = visit[x][y][c]+1
                dq.append((xx,yy,c+1))
            elif a[xx][yy]==0 and visit[xx][yy][c]==0:
                visit[xx][yy][c]= visit[x][y][c]+1
                dq.append((xx,yy,c))

먼저 이 로직은 입력된 K개에 따라, 벽을 부신 곳을 체크하는 곳인데 첨에는 0부터 시작하여 k개로 +1씩 체크하는 걸로 구현헤서 시간 초과가 나서 K개에서 0으로 -1씩 체크하는 걸로 구현하니 드디어 통과했다.

사실 +1씩 체크하는 거랑, -1씩 체크하는게 시간 복잡도 차이가 왜 나는지 생각해보고 찾아봐도 잘모르겠다...

정답 코드

import sys
input=sys.stdin.readline
from collections import deque
def BFS(x,y,z):
    dq=deque()
    dq.append((x,y,z))
    while dq:
        x,y,c=dq.popleft()
        if x == n-1 and y == m-1:
            return visit[x][y][c]
        for i in range(4):
            xx=x+dx[i]
            yy=y+dy[i]

            if xx<0 or xx>=n or yy < 0 or yy>=m:
                continue
            if a[xx][yy] == 1 and c >0 and visit[xx][yy][c-1]==0:
                visit[xx][yy][c-1] = visit[x][y][c]+1
                dq.append((xx,yy,c-1))
            elif a[xx][yy]==0 and visit[xx][yy][c]==0:
                visit[xx][yy][c]= visit[x][y][c]+1
                dq.append((xx,yy,c))
    return -1
                            
n,m,k=map(int, input().split())
a=[list(map(int, input().rstrip())) for _ in range(n)]

visit=[[[0]*(k+1) for _ in range(m)] for _ in range(n)]
visit[0][0][k]=1



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

print(BFS(0,0,k))