[카카오 2023 블라인드] 미로탈출명령어

독자는 BFS, DFS 알고리즘을 이해하고 있어야 하고, 해당 문제를 한번이라도 읽었어야 함

 

아이디어 도출 방법

문제의 조건을 체크해보면 아래의 조건이 존재합니다.

1. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
2. 같은 격자를 두 번 이상 방문해도 됩니다.
3. 격자의 범위를 나갈 순 없다.

우선 1번 조건을 수행하기 위해서 우선순위 힙을 이용해 방문 순서를 정렬했고, 항상 사전순으로 빠른 후보지를 선택할 수 있었다. 

 

같은 격자를 두 번이상 방문하는 것을 해결하는게 이 문제의 포인트였다.

같은 격자를 두 번 방문하게 되면 또 다시 4개의 선택지가 큐에 들어가기 때문에 탐색량이 많아지게 된다. 이런 문제를 해결하기 위해 가자치기를 수행했다. 

 

총 두 가지 가지치기를 수행했다.

```

1. 남은 이동 갯수와 도착 지점에서 목표 지점까지의 최단 거리를 비교했다 이 말은 탐색을 진행해도 목표지점까지 도달할 수 있는지 or 탐색을 진행해도 부족한 이동 개수로 인해 목표지점까지 도달하지 못하는지

 

2.  이동할 수 있는 거리 - 최단거리(도착지점에서 목표지점까지)를 빼고 홀수로 나오면 현재 도착지점에서는 k로 이동했을 때 k에 최단거리로는 도착할 수 없다. 따라서 이 경우를 제외한다. 

```

 

격자의 범위안인지 밖인지를 체크하는 방법은 아래의 코드에서 check_is_out_range를 확인하면 된다.

최종 결과

import heapq
from collections import defaultdict

def check_is_out_range(n_y, m_x, y, x):
    if (1 <= y <= n_y) and (1 <= x <= m_x):
        return False
    return True

def solution(n_y, m_x, x, y, r, c, k):
    y, x = x, y

    my = [-1, 0, 1, 0]
    mx = [0, 1, 0, -1]
    dir = ['u','r', 'd', 'l']
    
    heap = []
    heapq.heappush(heap, ["", y , x])

    while heap:
        state, y, x = heapq.heappop(heap)
        dist = abs(r - y) + abs(c - x)  #최단거리
        remain = k - len(state)

        if (remain - dist) % 2 is 1:
            continue

        if [y, x] == [r, c]:
            if remain is 0:
                return state
        
        if  dist >  remain:
            continue
        
        for d_y, d_x, d in zip(my, mx, dir):
            r_y = y + d_y
            r_x = x + d_x
            r_state = state + d

            if not check_is_out_range(n_y, m_x, r_y, r_x):
                heapq.heappush(heap, [r_state, r_y, r_x])

    return "impossible"

if __name__ == "__main__":
    n, m, x, y, r, c, k = [3, 4, 2 , 3 , 3, 1 ,5]
    print(solution(n, m, x, y, r, c, k))