[알고리즘] 백준 1600 Python

 

분류

BFS

혼자 힘으로 해결 했는가?

O

느낀 점

3차원 상태가 필요한 BFS 문제를 많이 풀다보니 이번 문제도 어렵지 않게 구상이 되었다.

크게 어렵지는 않았으며, 벽 부수고 이동하기와는 달리 K번까지 이동 가능한 부분만 잘 처리하면 된다.

---

 

내가 작성한 코드

from sys import stdin
from collections import deque

K = int(input())

W, H = map(int, input().split())

graph = []

for i in range(H):
    graph.append(list(map(int, stdin.readline().rstrip().split())))


MX = 1000001
visit = [[[1000001 for k in range(K + 1)] for col in range(W)] for row in range(H)]

horseDy = [-2, -1, 1, 2, 2, 1 , -1 ,-2]
horseDx = [1, 2, 2, 1, -1, -2, -2 ,- 1]

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

move = deque()

move.append((0,0,0,0))
visit[0][0][0] = 0

while move:
    y, x, z, count = move.popleft()
    # print("this y : %d, this x : %d, this z : %d, this count : %d" %(y,x,z,count))

    #그냥 이동
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if 0 <= ny < H and 0 <= nx < W:
            if visit[ny][nx][z] == MX and graph[ny][nx] != 1:
                visit[ny][nx][z] = count + 1
                move.append((ny,nx,z,count + 1))

    #말처럼 이동이 가능한가
    if z < K:
        # 말 처럼도 이동을 해보기
        for i in range(8):
            ny = y + horseDy[i]
            nx = x + horseDx[i]

            if 0<= ny < H and 0<= nx < W:
                # 말처럼 z번 이동해서 해당 좌표로 한번이라도 온적이 있으면 안됨
                if visit[ny][nx][z + 1] == MX and graph[ny][nx] != 1:
                    visit[ny][nx][z + 1] = count + 1
                    move.append((ny, nx, z + 1, count + 1))


result = min(visit[H - 1][W - 1])

# print()
# print(*visit[H-1][W-1])

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

 

 

 

---

비슷한 문제들

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

2206번: 벽 부수고 이동하기