[프로그래머스] 2023 KAKAO BLIND RECRUITMENT 미로 탈출 명령어 - Python

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

---

• 풀이
  • 우선 미로를 탈출 할 수 없는 경우와 있는 경우를 나누어 생각했다. 
    1. 미로를 탈출할 수 없는 경우 (impossible)
       • 출발지와 도착지의 최단거리를 계산 후 1) 남은 거리가 홀 수 또는 2) 최단거리가 k보다 멀다면 도착할 수 없다.
         • 남은 거리를 (d,u), (l,r) 쌍으로 채울 수 있는데 무조건 짝수여야한다.
    2. 미로를 탈출할 수 있는 경우
       • 문자열이 사전 순으로 가장 빠른 경로로 탈출
       • que를 사용하여 문자열이 빠른(d,l,r,u) 순으로 탐색한다. 이때 현 위치에서 도착지까지 남은 거리(k-이동 거리)로 갈 수 있는 경우만 생각해야한다.
       • 문자열이 빠른 경로로 탐색해야하므로 만약 ....d를 탐색한다면 ....l, ....r, ....u는 탐색할 필요가 없다.

• 코드

from collections import deque
def solution(n, m, x, y, r, c, k):
    # 불가능한 경우
    if (k-abs(x-r)+abs(y-c))%2 or abs(x-r)+abs(y-c) > k:
        return 'impossible'
    
    # 가능한 경우    
    # 이동방향 (아래(d), 왼쪽(l), 오른쪽(r), 위쪽(u))
    d = [['d',1,0],['l',0,-1],['r',0,1],['u',-1,0]]
    
    # que[i] : [path,cnt,cr,cc]
    que = deque()
    # 출발지 등록
    que.append(['',0,x,y])
    # 이동하기
    while que:
        # 현 위치
        path, cnt, cr, cc = que.popleft()
        # k번 이동해서 도착?
        if (cr,cc) == (r,c) and k == cnt:
            return path
        # 이동
        for p,dr,dc in d:
            # 이동 후 위치
            nr, nc = cr+dr, cc+dc
            # 범위 내
            if 0 < nr <= n and 0 < nc <= m:
                # 도착지까지 가능
                if cnt + abs(nr-r) + abs(nc-c) + 1 <= k:
                    que.append([path+p,cnt+1,nr,nc])
                    break