[프로그래머스] 미로 탈출 명령어 - Python (BFS)

https://school.programmers.co.kr/learn/courses/30/lessons/150365?language=python3

프로그래머스

 

주의할 점은 이미 방문한 칸도 '재방문'이 가능하다는 것이다. 이러한 경우에, 어처피 2차원 배열 안에서는 상,하,좌,우로만 이동하므로 맨하튼 거리를 이용하는 것이 최단거리가 될 것이다. 

따라서 맨하튼 최단 거리를 계산하여 k와 비교해주는 로직이 필요하다. 

또한 반드시 문자열은 사전순으로 빠른 순서이어야 하므로 처음부터 상하좌우에 해당하는 알파벳을 사전순으로 정렬한 순서인 하좌우상 으로 탐색해주어야 했다. 

from collections import deque 


def solution(n, m, x, y, r, c, k):
    answer = ''
    board = [['.'] * m for _ in range(n)]
    x, y, r, c = x-1, y-1, r-1, c-1
    
    def get_distance(a, b):
        return abs(a-r) + abs(b-c)

    board[x][y], board[r][c] = 'S', 'E'
    # 주의) 탐색 방향을 사전순으로 해야 한다 d, l, r, u
    dx = [1, 0, 0, -1]
    dy = [0, -1, 1, 0]
    literal = ['d', 'l', 'r', 'u']
    # 최단거리가 k 보다 작거나 ( 최단거리 - k )가 홀수 인 경우 
    if get_distance(x, y) > k or (get_distance(x, y)-k) % 2 == 1:
        return "impossible"
    
    queue = deque([])
    queue.append([x, y, '', 0])
    while queue:
        x, y, route, step = queue.popleft()
        if board[x][y] == 'E' and (k-step)%2 == 1: # 남은 거리가 홀수이면 되돌아 오지 못하므로 탈출 불가능 
            return "impossible"
        elif board[x][y] == 'E' and step == k:
            return route 
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if get_distance(nx, ny) + step + 1 > k:
                    continue
                queue.append([nx, ny, route+literal[i], step+1])
                break # 이미 사전순으로 정렬했으므로 여기서 break 걸어주어야 시간 초과를 방지할 수 있다! 
    return answer

 

카카오... 역시 맨하튼 거리 + 그래프 탐색 + 사전순 정렬로 시간 초과 방지 라는 생각해볼만한 점들이 많은 좋은 문제였다 !!