[백준] 14442 벽 부수고 이동하기 2 (파이썬 python)

 

 

문제 링크

 

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

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

 

 

문제 풀이

 

from collections import deque

def bfs():
    q = deque()
    q.append([0, 0, k])
    visited[0][0][k] = 1
    while q:
        x, y, z = q.popleft()
        if x == n - 1 and y == m - 1:
            return visited[x][y][z]
        for dir in range(4):
            nx, ny = x + dx[dir], y + dy[dir]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1 and z > 0 and visited[nx][ny][z - 1] == 0:
                    visited[nx][ny][z - 1] = visited[x][y][z] + 1
                    q.append([nx, ny, z - 1])
                elif graph[nx][ny] == 0 and visited[nx][ny][z] == 0:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    q.append([nx, ny, z])
    return -1

n, m, k = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]
visited = [[[0] * (k + 1) for _ in range(m)] for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
print(bfs())

 

 

기존에는 방문 체크 배열을 2차원으로 만들었으나,

부술 수 있는 벽의 개수를 추가하여 3차원 배열로 만들어줍니다.

방문 체크 배열은 방문 체크 뿐 아니라 거리 갱신을 함께 진행했습니다.

이 상태로 BFS를 실행하여, 만약 부술 수 있는 개수가 0보다 클 경우

개수를 1 줄여 visited 배열에 거리를 갱신해줍니다.

이렇게 반복하다 목표 지점에 도착했을 경우 거리를 반환해줍니다.

이동할 수 있는 곳을 모두 이동했음에도 목표 지점에 도착하지 못하면 -1을 반환해줍니다.