[백준 1600] 말이 되고픈 원숭이 - Python

문제 보기

[사용한 알고리즘]

BFS(너비 우선 탐색)

 

[문제 접근]

지도 상의 최단 거리를 구하는 문제는 대부분 DFS보다 BFS가 효율적이라 BFS로 접근하였습니다. DFS는 모든 경우를 탐색해야지 최단 경로인지 알 수 있기 때문입니다.

 

[알고리즘]

1. 현재 위치를 기준으로 상, 하, 좌, 우 이동합니다. (말의 형태로 이동이 가능한 상황이라면 말의 이동도 수행합니다)

2. 이동하려는 공간에 이전에 더 적은 말의 이동으로 도달한 적이 있다면 이동을 하지 않습니다.

3. 큐가 빌 때까지 혹은 도착지점에 도달할 때까지 위 과정을 반복합니다.

4. 도착지에 도달했으면 이동 횟수, 만약에 도달하지 못했으면 -1을 출력합니다.

 

[코드]

from collections import deque
import sys
sys.setrecursionlimit(10**8)

# 말처럼 이동
h_dx = [-1, -2, -2, -1, 1, 2, 2, 1]
h_dy = [-2, -1, 1, 2, 2, 1, -1, -2]

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs():
    q = deque()
    q.append((0, 0, 0, k))

    while q:
        x, y, cnt, remain_k = q.popleft()
        if remain_k >= 1:
            # 말처럼 이동
            for i in range(8):
                nx, ny = x + h_dx[i], y + h_dy[i]
                if 0 <= nx < h and 0 <= ny < w and maps[nx][ny] == 0:
                    if visited[nx][ny] == -1 or visited[nx][ny] < remain_k - 1:
                        if nx == h - 1 and ny == w - 1:
                            return cnt + 1
                        visited[nx][ny] = remain_k - 1
                        q.append((nx, ny, cnt + 1, remain_k - 1))
        # 상, 하, 좌, 우 이동
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maps[nx][ny] == 0:
                if visited[nx][ny] == -1 or visited[nx][ny] < remain_k:
                    if nx == h - 1 and ny == w - 1:
                        return cnt + 1
                    visited[nx][ny] = remain_k
                    q.append((nx, ny, cnt + 1, remain_k))
    return -1


if __name__ == "__main__":
    k = int(sys.stdin.readline())
    w, h = map(int, sys.stdin.readline().split())
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]
    visited = [[-1] * w for _ in range(h)]

    if w == 1 and h == 1:
        print(0)
    else:
        print(bfs())