[KAKAO/Python] 미로 탈출 명령어

- 처음부터 greedy나 dfs로 접근했으면 더 쉬웠을 것 같은 문제

- bfs로 접근하려면, 항상 최단거리로 이동한다는 가정을 가지고 적절하게 return과 break를 걸어줘야 TLE가 발생하지 않는다

'''
condition
- TL : ?
- 2<=n,m<=50, 1<=x,r<=n, 1<=y,c<=m
- S와 E는 다른 위치다
- 1 <=k <=2,500
- move
    - (x,y)에서 (r,c)로 이동함
    - 격자 바깥으로 나갈 수 없음
    - 총 이동거리는 k여야하고, 중복이 허용된다
    - 이동경로의 상하좌우 = u,d,l,r (사전순: d<l<r<u)

goal
- 이동 경로중에서 사전순으로 가장 빠른 경로를 return하여라
- 탈출 불가능하다면 "impossible"을 return

approach
1) bfs
- 최단거리이므로 bfs를 사용해보자
- 이때 중복을 허용해야하므로 visited를 사용하지않고, 이동거리<k로 제한한다

2) bfs
- 최단거리를 한번 갱신했다면, 이후 탐색부터는 최단거리와 비교해서 걸러내는 작업을 진행한다

3) bfs
- 현재 상태에서 남은 거리와, k-move_cnt를 비교해서 걸러내는 작업을 진행한다

4) greedy
- d,l,r,u 순으로 이동하면 무조건 최단거리가 나오므로, for문 탐색에서 조건을 만족하는 순간 break 걸어버린다
- 마찬가지로 도착 가능 여부 확인하고 계속 continue할 필요 없이 return시킨다

'''
from collections import deque


def check_condition(r,c,nr,nc,k,move_cnt):
    # 도착지점까지 남은 거리와, 이동 가능한 횟수를 비교
    remain_cnt = abs(r-nr) + abs(c-nc)
    possible_cnt = k-move_cnt
    # 가능 횟수 < 남은 횟수 : false
    if possible_cnt < remain_cnt:
        return False
    # 가능 횟수 > 남은 횟수 : true
    return True


def bfs(n,m,x,y,r,c,k):
    move_cnt = 0
    route = ""
    dq = deque()
    dq.append((x,y,move_cnt,route)) # 시작점r, 시작점c, 이동횟수, 이동경로
    # 탐색 시작
    while dq:
        cr,cc,move_cnt,route = dq.popleft()
        # 도착 가능 여부 확인
        if (cr,cc)==(r,c):
            # 정확히 도착한 경우 -> 경로를 return
            if k == move_cnt:
                return route
            # 거리가 남는데 홀수인 경우 -> 도착 불가능, impossible을 return
            elif (k-move_cnt) %2 != 0:
                return "impossible"    
            
        # d,l,r,u 순서로 이동 
        for i in [1,2,3,0]:
            nr,nc = cr+dr[i], cc+dc[i]
            # 이동 가능 조건
            if not(0<nr<=n and 0<nc<=m) or move_cnt >= k or not check_condition(r,c,nr,nc,k,move_cnt+1):
                continue
            # 조건을 만족하는 경우 -> (d,l,r,u)로 이동하므로, 조건 만족하면 무조건 최단경로이다
            dq.append((nr,nc,move_cnt+1,route+moveDir[i]))
            break
    return "impossible"

            
def solution(n, m, x, y, r, c, k):
    global graph, dr, dc, moveDir, remainDir
    # setting
    graph = [[0]*(m+1) for _ in range(n+1)]
    dr = [-1,1,0,0]
    dc = [0,0,-1,1]
    moveDir = ['u','d','l','r']
    remainDir = ['ud', 'du', 'lr', 'rl']
    # bfs 실행해서 최단경로를 탐색
    return bfs(n,m,x,y,r,c,k)