백준 14442번 : 벽 부수고 이동하기2 - 파이썬 Python

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

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

 

생각하기

bfs 방식을 통해서 가장 먼저 목적지에 도착하면 해당 카운트를 return 하는 방식으로 생각

벽을 부순 횟수 K번에 대한 각각의 visited를 따로 구별해서 표현해야

 

• visited[횟수][row][col]

벽 부순 횟수에 따라 row와 col에 방문한 적이 있는가 체크하여 방문하였으면 중복해서 방문하는 케이스를 줄인다. 

 

 

구상하기

큐를 사용하여 bfs를 구상한다 단, 실수를 할 수 있는 부분이 있다.

 

• 큐에서 pop한 경우, 바로 목적지인지 검사하기

바로 1x1의 칸이 초기값으로 주어졌을 때이다.

이 경우 bfs 함수에 들어가자마자 끝나야 하는 것이 정상인데 

만약 col, row가 목적지인지 검사하는지 체크하는 부분이 뒤쪽에 위치한다면 해당 부분에서 오류가 날 수 있음

 

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

N, M, K = map(int, input().split())

visited = [[[0 for col in range(M)] for row in range(N)]for depth in range(K+1)]

data = []
for col in range(N):
    data.append(list(map(int, input().strip())))



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

def bfs(col, row):
    q = deque()
    visited[0][col][row]= 1
    q.append((col, row, 0))

    while q:
        c, r, crash_cnt = q.popleft()

        if c == N-1 and r == M-1:
            return visited[crash_cnt][c][r]

        for i in range(4):
            nc = c + dy[i]
            nr = r + dx[i]

            if nc < 0 or nc >= N or nr < 0 or nr >= M:
                continue
 
            if data[nc][nr] == 0 and visited[crash_cnt][nc][nr]==0: # 벽이 아닌 경우
                q.append((nc, nr, crash_cnt))
                visited[crash_cnt][nc][nr] = visited[crash_cnt][c][r]+1

            if data[nc][nr] == 1 and crash_cnt+1 <= K and visited[crash_cnt+1][nc][nr] == 0: # 벽인 경우
                q.append((nc, nr, crash_cnt+1))
                visited[crash_cnt+1][nc][nr] = visited[crash_cnt][c][r]+1
                
    return -1


print(bfs(0, 0))