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

문제 풀러 가기

풀이 🍅

| 한 마디로 하면 벽 부수고 이동하기 문제와 비슷하게 풀었다!
일단 최단 거리를 알아내는 문제니까 BFS로 풀어야 겠다고 생각했다. 그런데 특이한 것은 K번까지 말의 움직임처럼 움직일 수 있다는 것이다.
벽도 있으니까,, 무조건 K번 말의 움직임을 다 쓴다고 최소 동작으로 목적지까지 가는 것도 아니고.. 어쩌면 0번 말처럼 움직였을 때가 최소 동작일 수도 있을 것이다. 그래서 몇 번 말처럼 움직였는지를 고려해서 visit 체크를 3차원 리스트로 만들었다. K는 최대 30이니까 괜찮다 !
나머지는 일반적인 BFS처럼 하면 된다.

코드 🖥

import sys
from collections import deque

input = sys.stdin.readline

dx, dy = [0, 0, -1, 1], [1, -1, 0, 0]
hx, hy = [-2, -2, -1, 1, 2, 2, -1, 1], [-1, 1, -2, -2, -1, 1, 2, 2]


def bfs():
    q = deque()
    q.append((0, 0, K, 0))  # 맨 왼쪽 위에서 시작 - 인덱스, 말처럼 움직일 기회가 몇번 남았는지, 이동 횟수

    visited = [[[False] * (K + 1) for _ in range(W)] for _ in range(H)]  # 세로 좌표, 가로 좌표, 남은 점프 횟수
    visited[0][0][K] = True
    while q:
        i, j, k, cnt = q.popleft()

        # 목적지 도착했으면
        if i == (H - 1) and j == (W - 1):
            return cnt

        # 말처럼 이동 가능하면
        if k > 0:
            for m in range(8):
                ni, nj = i + hx[m], j + hy[m]

                    # 범위 체크, 방문 체크, 목적지가 장애물이면 이동 불가능
                if 0 <= ni < H and 0 <= nj < W and arr[ni][nj] == 0 and visited[ni][nj][k - 1] == False:
                    visited[ni][nj][k - 1] = True
                    q.append((ni, nj, k - 1, cnt + 1))

        # 사방으로 이동
        for m in range(4):
            ni, nj = i + dx[m], j + dy[m]

            # 범위 체크, 방문 체크, 목적지가 장애물이면 이동 불가능
            if 0 <= ni < H and 0 <= nj < W and arr[ni][nj] == 0 and visited[ni][nj][k] == False:
                visited[ni][nj][k] = True
                q.append((ni, nj, k, cnt + 1))

    # 도착점 도착할 수 없으면
    return -1


K = int(input())
W, H = map(int, input().split())
arr = tuple(tuple(map(int, input().split())) for _ in range(H))
print(bfs())

소감

ㅠㅠㅠㅠㅠ 드디어 맞았다 !!!!!!!!!
계속 파이썬은 시간초과, 파이파이는 메모리 초과 나서 힘들었다. 시간 계산해봐도 시간 초과 안날 것 같은데 계속 나서 답답했다.ㅠㅠ
결론은 코드를 잘못 써서 그런 거였다.. 역시 내가 실수를 하고, 컴퓨터는 실수를 하지 않는다...

나는 계속 시간 초과가 나길래,, 내가 코드를 잘못 짠 것이 아니라 시간 초과가 나서 문제인 줄 알았다. 그래서 시간을 줄이려고 엄청 노력했다.. arr를 리스트가 아니라 tuple로 하고, 함수를 만들어서 부르는 데도 시간이 든다고 해서 bfs 함수도 없애고 그냥 쭉 코드 짜는 등등.. 그런데 계속 안됐다.

내가 잘못 했던 부분은
말처럼 이동할 때 if 0 <= ni < H and 0 <= nj < W and arr[ni][nj] == 0 and visited[ni][nj][k - 1] == False: 부분에서 visited[ni][nj][k - 1] == False를 visited[ni][nj][k] == False로 쓴 것이었다..!! 말처럼 한 번 더 움직이려고 하는 상황에서 방문했는지를 봐줘야 하는 거니까 k가 아니라 k-1로 해야 한다.

그리고 q.popleft한 후에(큐에서 뺄 때) 목적지에 도착했는지 체크하지 않고, ni, nj를 만든 후에(큐에 넣기 전에) 목적지 도착 체크를 했었다. 그랬더니 H, W 가 1인 경우에 틀렸다. 그럴 때는 큐에서 빼기만 하고, 큐 안에 넣지 않기 때문이다. 그래서 지금처럼 큐에서 뺄 때 목적지 도착 체크하는 것으로 바꾸니까 맞았다!