[백준 2024/10/18] 1600번 말이 되고픈 원숭이

1. 문제

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

 

2. 접근 방법

처음에 i, j 로 visited list를 만드는 것을 생각하였다가, k의 값이 유동적일 것이라 힘들 것 같다는 생각을 하였었다.

하지만 3차원 리스트가 존재했기 때문에, 이를 이용하면 되었다.

 

코드 풀이 중에서 처음 시도는 

import queue

를 하는 것이었다. 하지만, 시간 초과와 런타임 에러가 지속되었고 다른 코드를 확인하다가 

 

from collections import deque

를 적용한 코드를 확인하게 되었다.

 

이에 queue -> deque로 import를 바꾸었고, 통과할 수 있었다.

 

과연, 둘의 차이가 무엇일까?

 

1. import queue
   queue.Queue()로 사용이 된다. 이는 멀티스레딩 환경에서의 큐로 적합하게 이용이 된다.
   또한, 멀티스레딩 환경에서의 안전을 보장하기 위해 락 메커니즘을 사용한다. 시간 복잡도가 O(1)이긴 하지만, 스레드 안정성을 보장하기 위한 추가 작업 때문에 성능이 조금 떨어진다.
   
   
2. from collections import deque
   deque는 양방향 큐로 양쪽 끝에서 빠르고 효율적인 추가가 가능하다. O(1)의 시간 복잡도를 보장하나, 스레드 안전성을 보장하지 않는다.

 

따라서, 해당 문제는 싱글 쓰레드에서 실행이 되므로, import queue보다는 from collections import deque를 사용해서 시간적으로 이점을 얻는 것이 낫다.

 

3. 코드

from collections import deque

q = deque()


def bfs(k):
    monkey = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    horse = [(-2, -1), (-1, -2), (1, -2), (2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1)]
    visited = [[[0 for col in range(w)] for row in range(h)] for depth in range(k+1)]

    q.append((0, 0, k, 0))

    while q:
        i, j, k, cnt = q.popleft()
        if visited[k][i][j] == 1:
            continue

        visited[k][i][j] = 1

        if i == h - 1 and j == w - 1:
            return cnt

        for l, r in monkey:
            if 0 <= i + l < h and 0 <= j + r < w and plain[i + l][j + r] == 0 and visited[k][i+l][j+r] == 0:
                q.append((i+l, j+r, k, cnt+1))

        if k > 0:
            for l, r in horse:
                if 0 <= i + l < h and 0 <= j + r < w and plain[i + l][j + r] == 0 and visited[k-1][i+l][j+r] == 0:
                    q.append((i+l, j+r, k-1, cnt+1))

    return -1


if __name__ == "__main__":
    k = int(input())
    w, h = map(int, input().split())
    plain = []

    for _ in range(h):
        plain.append(list(map(int, input().split())))

    print(bfs(k))