[BFS] 백준 1600번 : 말이 되고픈 원숭이 - 파이썬 Python

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

1600번: 말이 되고픈 원숭이

생각하기

처음에는 말의 움직임과 원숭이 본래 움직임을 통합하여 BFS로 풀고자 하였다.

 

하지만 간과한 사안이 있었다. 

말의 움직임과 원숭이 본래 움직임이 전혀 다른 패턴이기 때문에 

원숭이의 본래 움직임으로 방문한 칸을 나중에 말의 움직임으로 더 짧은 시간에 방문할 수 있다는 점이었다.

 

만약 움직임의 패턴이 다른 경우, 

칸까지 움직인 최소 거리를 하나의 visited 배열에 넣는 방식을 취한다면, 

• 말의 움직임으로 이동했을 때, 짧은 경우 visited에 이미 거리가 존재하는 경우 갱신 못함
• 기존 visited에 거리가 존재하는 경우, 거리 비교를 통해 작은 거리로 대체한다고 하더라도 큐에 들어있는 다른 vertex들에게 혼동을 주어서 무한 반복하게 되는 상황을 만든다

 

그럼 어떻게 서로 다른 이동 패턴들이 겹치지 않게 나눌 것인가

 

원숭이가 말의 움직임을 따라할 수 있는 횟수는 K번으로 정해져 있다

따라서 해당 횟수를 기준으로 visited 배열을 나누어서 관리하면 된다

 

구현하기

3차원 배열을 선언하여 K횟수에 따라서 구분한다

visited[K][i][j] 는 아직 한번도 말의 움직임을 사용하지 않았을 때의 (즉, 원숭이 본래 움직임으로만 BFS) 각 칸까지의 최소 거리

visited[K-1][i][j] 는 한번 말의 움직임을 사용했을 때의 각 칸까지의 최소 거리

 

이런식으로 구하고 각 visited에서 i == H-1 / j == W-1 인 경우 

최솟값 ans를 업데이트 하는 방식을 가진다

 

정점(row, col, cnt, horse_move) 

horse_move - 말 처럼 이동할 수 잇는 남은 횟수

 

시간 복잡도

200 * 200 * 30 = 1200000 -> BFS로 해결 충분히 가능

 

# 원숭이는 K번만 말과 같이 움직일 수 있음 -> 나머지는 인접한 칸(상, 하 좌, 우)
# 원숭이는 맨왼쪽 위에서 맨 오른쪽 아래로 이동

# 말의 움직임 (K번만 사용 가능, 장애물 뛰어넘을 수 있음
# 상하좌우로 움직이는 것

# 최소한으로 시작지점에서 도착지점까지 갈 수 있는 방법
from collections import deque

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

grid = []
for _ in range(H):
    grid.append(list(map(int, input().split())))

# 0 평지 / 1은 장애물

# 시간 복잡도
## 200 * 200 = 40000

horse_dx = [2, 1, 2, 1, -1, -2, -1, -2]
horse_dy = [1, 2, -1, -2, 2, 1, -2, -1]

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



# (row 좌표, col 좌표, 횟수, 말처럼이동가능 남은 횟수)

def bfs():
    visited = [[[-1]*W for _ in range(H)]for k in range(K+1)]
    q = deque()
    q.append((0, 0, 0, K))
    visited[K][0][0] = 0

    ans = int(1e9)
    while q:
        row, col, cnt, horse_move = q.popleft()

        if row == H-1 and col == W-1:
            ans = min(ans, cnt)
            continue

        # 말처럼 움직일 수 있을 때
        if horse_move > 0:
            for d in range(8):
                nrow = row + horse_dx[d]
                ncol = col + horse_dy[d]

                if nrow<0 or nrow>=H or ncol<0 or ncol>=W or visited[horse_move-1][nrow][ncol] != -1 or grid[nrow][ncol] == 1:
                    continue
                
                q.append((nrow, ncol, cnt+1, horse_move-1))
                visited[horse_move-1][nrow][ncol] = cnt+1


        # 원숭이 move 일 때,
        for d in range(4):
            nrow = row + dx[d]
            ncol = col + dy[d]

            if nrow<0 or nrow>=H or ncol<0 or ncol>=W or visited[horse_move][nrow][ncol] != -1 or grid[nrow][ncol] == 1:
                continue

            q.append((nrow, ncol, cnt+1, horse_move))
            visited[horse_move][nrow][ncol] = cnt+1


        
    if ans == int(1e9):
        return -1
    else:
        return ans

print(bfs())