[백준] 1600.말이 되고픈 원숭이 🐵

[백준] 1600.말이 되고픈 원숭이 🐵 바로가기

아이디어

처음 아이디어

• 말로 이동을 하면 더 많이 이동할 수 있으니 말로 이동을 먼저한다. -> 안되면 원숭이로 이동한다

문제점

격자판에는 벽(1)이 존재하기 때문에, 앞에서 이미 말로 이동할 수 있는 횟수를 다써버리면 말로 도착해야할 때(장애물을 만났을 때) 갈 수 없는 문제가 생겼다....

예시)
0 0 1 0 0 1 0 0 1 0
0 0 1 1 0 0 0 0 1 0

○ ○ 1 ● ● 1 ○ ○ 1 ●
● ● 1 1 ● ● ● ● 1 ●

해결 방법

1. 원숭이로 이동한다.
2. K번을 채울 때까지 말로 이동할 수 있는지 체크한다.
3. visited 배열을 3차원으로 만들었다.
   -> [말X 이동횟수, 1번째 말로 이동횟수, ... K번째 말로 이동횟수]

visited = [[[0] * (K + 1) for _ in range(W)] for _ in range(H)] 
 # visited[h][w][가는 방법] => board[h][w][k]를 갈 때 걸리는 동작 횟수

# 예시) K == 2라면
# 0 1 0
# 0 0 0
# [말로 이동안할 때, 말로 이동할 때] 
[[[1, 0], [0, 0], [0, 0]
  [2, 0], [0, 0] [0, 2]]]

-> 지금 내 레벨로는 생각 못해낼 것 같다.... 🤯

시간 복잡도

BFS를 수행하는 데 필요한 기본적인 단계는 보드의 모든 칸 O(W * H)
그러나 각 위치마다 추가적으로 최대 K번의 말처럼 이동을 확인해야 할 수 있어서 시간 복잡도는 O(W * H * K)

코드

1. 다음 이동 지점이 도착지점인지 확인
   -> 출발하자마자 도착지점일 경우 예외처리 필요함

from collections import deque
import sys
input = sys.stdin.readline

# 이동 가능한지 체크
def check(nh, nw, k):
    if 0 <= nh < H and 0 <= nw < W and not visited[nh][nw][k] and board[nh][nw] == 0:
        return True


# 이동(bfs)
def move():
    q = deque([(0, 0, 0)])
    visited[0][0][0] = 1

    while q:
        h, w, k = q.popleft()

        # 원숭이로 이동(상하좌우)
        for i in range(4):
            nh = h + monkey_dh[i]
            nw = w + monkey_dw[i]

            if check(nh, nw, k):
                # 도착
                if (nh, nw) == (H - 1, W - 1):
                    return visited[h][w][k]
                # 이동횟수 + 1
                visited[nh][nw][k] = visited[h][w][k] + 1
                q.append((nh, nw, k))


        # 말처럼 이동
        if k < K:
            for j in range(8):
                nh = h + horse_dh[j]
                nw = w + horse_dw[j]

                if check(nh, nw, k + 1): # 한 칸옆을 확인해줘야한다.
                    # 도착
                    if (nh, nw) == (H - 1, W - 1):
                        return visited[h][w][k]
                    
                    q.append((nh, nw, k + 1))
                    visited[nh][nw][k + 1] = visited[h][w][k] + 1

    return -1


K = int(input())
W, H = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(H)]
visited = [[[0] * (K + 1) for _ in range(W)] for _ in range(H)] 

# 말처럼 이동
horse_dh = [-2, -1, 1, 2, 2, 1, -1, -2]
horse_dw = [1, 2, 2, 1, -1, -2, -2, -1]

# 원숭이 이동
monkey_dh = [-1, 1, 0, 0]
monkey_dw = [0, 0, -1, 1]

# 원숭이 시작
# 시작하자마자 도착일 때 예외처리(nw, nh일 때 종료조건 걸기 위해서 -> 동작횟수 줄일 것 같아서)
if len(board) == 1 and board[0][0] == 0:
    print(0)
    exit(0)

# 아니면 이동하러 가기
print(move())

2. popleft했을 때 도착지점인지 확인
   (따로 예외처리 필요없음, 시간 차이도 별로 없음)

from collections import deque
import sys
input = sys.stdin.readline

# 이동 가능한지 체크
def check(nh, nw, k):
    if 0 <= nh < H and 0 <= nw < W and not visited[nh][nw][k] and board[nh][nw] == 0:
        return True


# 이동(bfs)
def move():
    q = deque([(0, 0, 0)])
    visited[0][0][0] = 1

    while q:
        h, w, k = q.popleft()

        # 도착
        if (h, w) == (H - 1, W - 1):
            return visited[h][w][k] - 1

        # 원숭이로 이동(상하좌우)
        for i in range(4):
            nh = h + monkey_dh[i]
            nw = w + monkey_dw[i]

            if check(nh, nw, k):
                # 이동횟수 + 1
                visited[nh][nw][k] = visited[h][w][k] + 1
                q.append((nh, nw, k))


        # 말처럼 이동
        if k < K:
            for j in range(8):
                nh = h + horse_dh[j]
                nw = w + horse_dw[j]

                if check(nh, nw, k + 1): # 한 칸옆을 확인해줘야한다.
                    q.append((nh, nw, k + 1))
                    visited[nh][nw][k + 1] = visited[h][w][k] + 1

    return -1


K = int(input())
W, H = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(H)]
visited = [[[0] * (K + 1) for _ in range(W)] for _ in range(H)] 

# 말처럼 이동
horse_dh = [-2, -1, 1, 2, 2, 1, -1, -2]
horse_dw = [1, 2, 2, 1, -1, -2, -2, -1]

# 원숭이 이동
monkey_dh = [-1, 1, 0, 0]
monkey_dw = [0, 0, -1, 1]

# 원숭이 시작
print(move())