[boj 1600][Python] 말이 되고픈 원숭이

링크

메모

아래로 바로 문제에 대한 요약 갑니당.

• 말처럼 움직이는 방법에 대하여

  • 처음에 이중포문 쓰면서 4*2가지 나오도록 함
  • 다른사람 코드 보니 아예 8가지에 대해 x, y 가감값을 리스트로 저장해놓고 가져옴
  • 그게 더 빠를 거 같음 ㅇㅈ

• k번은 어떻게 체크할 것인가?

  • 이에 대해서, 이전에 풀었던 문제인 벽 부수고 이동하기 를 참고한다.
  • 약간 이해하기가 복잡한데, 이동 지점에 k에 대해 몇번 남아있는지 정보가 꼭 있어야 한다.
  • 따라서, visited를 3차원으로 관리하며, 큐에 넣는 값도 3개의 원소로 한다.

• 맞왜틀?

  • 마지막 트러블 슈팅을 하는데 왜 안 되는 건지 헤맸다.
  • 조건 하나 안 써서 자꾸 시간초과 난 거였음.
  • 진행할 수 있는 조건이 복잡하므로, 조건을 빼먹은 게 있지 않는지 (if문 여러개 쓰고 등등) 체크한다.

• 최단경로는 대체로 bfs

  • dfs와의 차이를 생각하면, 얕은 depth부터 보는 bfs가 더 빠르다.

코드

# 1600 말이 되고픈 원숭이

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

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

d1 = [-2, -1, 1, 2, 2, 1, -1, -2]
d2 = [1, 2, 2, 1, -1, -2, -2, -1]

k = int(input())
w, h = map(int, input().split())
graph = [[] for _ in range(h)]
for i in range(h):
    graph[i] = list(map(int, input().split()))

# 함수정의
# def getMove(d1, d2, x, y):
#     # d1, d2에 따라 8방향 이동.
#     if d1 == 0 or d1 == 1:
#         # 좌우로 2칸 이동 + 상하로 1칸 이동
#         a = x + 2*dx[d1]
#         b = y + d2
#     else:
#         a = x + d2
#         b = y + 2*dy[d1]
#     return (a, b)


def isValid(x, y):
    if x<0 or x>=h or y<0 or y>=w:
        return False
    else:
        return True


def bfs(graph, k):
    # 0, 0에서 h,w 까지
    # return: 최소횟수
    left = k

    q = deque()
    q.append((0, 0, k))
    visited = [[[0 for _ in range(31)] for _ in range(w)] for _ in range(h)]

    while q:
        x, y, z = q.popleft()
        if x == h-1 and y == w-1:
            return visited[x][y][z]
        for d in range(4):
            xx = x + dx[d]
            yy = y + dy[d]
            if isValid(xx, yy):
                if graph[xx][yy] != 1 and visited[xx][yy][z] == 0:
                    q.append((xx, yy, z))
                    visited[xx][yy][z] = visited[x][y][z] + 1
        if z > 0:
            for d in range(8):
                xx = x + d1[d]
                yy = y + d2[d]
                if isValid(xx, yy):
                    if graph[xx][yy] != 1 and visited[xx][yy][z-1] == 0:
                        q.append((xx, yy, z-1))
                        visited[xx][yy][z-1] = visited[x][y][z] + 1
        
    return -1


print(bfs(graph, k))