말이 되고픈 원숭이

풀이

 최단거리를 구하는 BFS 문제다. 이전까지 내가 풀어본 BFS 문제에서는 대부분 visited 리스트를 전역으로 하나 만들어서 풀이 전반에 걸쳐 사용했었다. 하지만 이 문제에서는 같은 좌표라도 말이 몇번 되었는지에 따라 거리가 달라진다. 따라서 처음에는 경로마다 visited 리스트를 할당해 값을 갱신했었다. 하지만 메모리 초과 판정이 떴다. 곰곰이 생각하다가 스터디에서 BFS 문제에서 3차원 리스트에 관해 들었던게 생각나서 이를 활용해서 코드를 수정했고 결국 풀었다.

from collections import deque
import sys

k = int(input())
w, h = map(int, input().split())
graph = []

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

# 동 서 남 북
dx = [0, 0, 1, -1,-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, -1, 0, 0, 1, 2, 2, 1, -1, -2, -2, -1]
visited =[[[False] * w for _ in range(h)] for _ in range(k+1)]

def bfs(x, y, count,k):
    queue = deque([(x,y, count,k)])
    visited[k][x][y] = True
    while(queue):
        x,y,count,k = queue.popleft()
        if x == h - 1 and y == w - 1:
            print(count)
            return
        # 동 서 남 북 이동
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<h and 0<=ny<w:
                if visited[k][nx][ny]==False and graph[nx][ny]==0:
                    queue.append((nx, ny, count + 1, k))
                    visited[k][nx][ny] = True
        # 체스 나이트 이동
        if k > 0:
            for i in range(4, 12):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < h and 0 <= ny < w:
                    if visited[k-1][nx][ny]==False and graph[nx][ny]==0:
                        queue.append((nx, ny, count + 1, k-1))
                        visited[k-1][nx][ny] = True
    print(-1)
    return

bfs(0, 0, 0, k)

시간복잡도 : O(kwh)