[TIL_Carrotww] 119 - 23/06/07

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 말이 되고픈 원숭이

BFS 문제를 많이 풀다보니 이렇게 다양한 방법으로 이동하는 문제에 대해서는 3차원 배열로 접근하여 풀면 풀린다는걸 알고 있어서 그렇게 접근했더니 바로 풀렸다.

체스 말처럼 이동하는 말의 움직임은 8개밖에 없으므로 hr, hc로 배열을 만들어 움직임 배열을 선언하고 8번 돌려가며 지도 안에 있는지 visited에 jump 수를 체크하여 계산해 주었다.

hr, hc = [2, 2, -2, -2, 1, -1, 1, -1], [-1, 1, -1, 1, 2, 2, -2, -2]

위와 같이 작성해주면 말처럼 이동하는 모든 방향에 대한 정보를 담아줄 수 있다.

• 풀이

def solve():
    import sys
    from collections import deque
    K = int(sys.stdin.readline())
    c, r = map(int, sys.stdin.readline().split())
    graph = []
    for _ in range(r):
        graph.append(list(map(int, sys.stdin.readline().split())))

    queue = deque()
    queue.append([0, 0, 0, 0])
    visited = [[[False] * (K + 1) for _ in range(c)] for _ in range(r)]
    dr, dc = [1, -1, 0, 0], [0, 0, 1, -1]
    hr, hc = [2, 2, -2, -2, 1, -1, 1, -1], [-1, 1, -1, 1, 2, 2, -2, -2]

    while queue:
        cur_r, cur_c, cnt, jump = queue.popleft()
        if cur_r == r - 1 and cur_c == c - 1:
            print(cnt)
            return
        for direct in range(4):
            n_r, n_c = cur_r + dr[direct], cur_c + dc[direct]
            if (n_r < 0 or n_r >= r) or (n_c < 0 or n_c >= c) or graph[n_r][n_c] == 1 or visited[n_r][n_c][jump]:
                continue
            visited[n_r][n_c][jump] = True
            queue.append([n_r, n_c, cnt+1, jump])
        if jump < K:
            for direct in range(8):
                n_r, n_c = cur_r + hr[direct], cur_c + hc[direct]
                if (n_r < 0 or n_r >= r) or (n_c < 0 or n_c >= c) or graph[n_r][n_c] == 1 or visited[n_r][n_c][jump+1]:
                    continue
                visited[n_r][n_c][jump+1] = True
                queue.append([n_r, n_c, cnt+1, jump+1])

    print(-1)
    return

if __name__ == "__main__":
    solve()

visited를 3차원으로 두고 3차원에는 몇번 뛰었던 원숭이가 왔는지?를 체크하며 BFS를 돌렸다.