[알고리즘] 백준 14442 Python

 

분류

BFS

혼자 힘으로 해결 했는가?

O

느낀 점

이제 이러한 비슷한 3차원 BFS문제는 크게 어렵지 않게 풀수 있을것 같다.

비슷한 문제는 1600번인데, 해당 문제와 차이점은 z축으로 추가적인 이동을 하기 위해서는 이동하는 그래프가

벽일 때만 가능하도록 해줘야 한다는 것이다.

---

 

내가 작성한 코드

from sys import stdin
from collections import deque

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

MX = 10000001
graph = []
visit = [[[MX for k in range(K + 1)] for col in range(M)]for row in range(N)]

for i in range(N):
    graph.append(list(stdin.readline().rstrip()))

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

move = deque()

visit[0][0][0] = 1

move.append((0,0,0,1))

while move:

    y, x, k, time = move.popleft()

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if 0<= ny < N and 0<= nx < M:
            # 벽 안부수고 이동
            if visit[ny][nx][k] == MX and graph[ny][nx] != '1':
                visit[ny][nx][k] = time + 1
                move.append((ny,nx,k,time + 1))

            # 벽 부수고 이동
            if k < K and visit[ny][nx][k + 1] == MX and graph[ny][nx] == '1':
                visit[ny][nx][k + 1] = time + 1
                move.append((ny,nx,k + 1, time + 1))


result = min(visit[N-1][M-1])

if result == MX:
    print(-1)
else:
    print(result)

 

 

 

---

비슷한 문제들

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

1600번: 말이 되고픈 원숭이