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

미로 탈출 명령어

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150365

접근 방식

DFS

맨 처음은 단순 DFS로 풀어보려 했지만 k의 값이 너무 커서 시간 초과가 일어났다.

import sys
sys.setrecursionlimit(10 ** 6)

from collections import deque

def solution(n, m, x, y, r, c, k):
    DIRECTIONS = ['d', 'l', 'r', 'u']
    dx, dy = [1, 0, 0, -1], [0, -1, 1, 0]
    
    stack = deque([])
    stack.append([x, y, ''])
    
    while stack:
        cx, cy, moves = stack.pop()
        
        if len(moves) > k:
            continue
        
        if cx == r and cy == c:
            if len(moves) == k:
                return moves
            elif (k - len(moves)) % 2 == 1:
                continue
        
        temp = []
        
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 < nx <= n and 0 < ny <= m:
                temp.append([nx, ny, moves + DIRECTIONS[i]])
        
        temp.reverse()
        stack += temp
    
    return 'impossible'

구현

조건에 신경 쓰면 백트래킹으로 해결할 수도 있는 문제였는데 (몰랐다),
나는 규칙을 찾아내서 O(1)에 해결할 수도 있다는 생각에 꽂혔다.

이 문제에서 출발 위치와 탈출 지점의 맨해튼 거리를 초과하는 k가 주어졌을 때 사전 순으로 가장 빠른 경로는 다음과 같다.

1. 우선 최대한 (k값에 여유가 있는 한) 밑으로 많이 간다.
2. 그 다음 최대한 왼쪽으로 많이 간다.
3. 미로의 가장 왼쪽 밑에 도달해도 k값에 여유가 있으면 우로 한 칸 갔다 좌로 한 칸 갔다를 반복한다. (그 위치에 도달하면 'rl'이 최선)
4. 오른쪽으로 c까지 간다.
5. 위로 r까지 간다.

def solution(n, m, x, y, r, c, k):
    counts = {'d': 0, 'l': 0, 'r': 0, 'u': 0}
    extra = '' # 3번에 해당
    
    x_diff, y_diff = r - x, c - y
    x_direction = 'u' if x_diff < 0 else 'd' # 탈출 지점의 방향
    y_direction = 'l' if y_diff < 0 else 'r' # 탈출 지점의 방향
    
    # 아래, 왼쪽 벽과의 거리
    x_wall, y_wall = min(n - x, n - r), min(y, c) - 1 
    
    # 맨해튼 거리를 초과하는 이동 수
    extra_moves = k - (abs(x_diff) + abs(y_diff))

    if extra_moves < 0 or extra_moves % 2 == 1:
        return 'impossible'
    
    # 탈출 지점까지 이동
    counts[x_direction] += abs(x_diff)
    counts[y_direction] += abs(y_diff)

	# 1번 & 5번
    if extra_moves > x_wall * 2: # 여유가 있다면 벽을 찍고 돌아오고
        counts['d'] += x_wall
        counts['u'] += x_wall
        extra_moves -= x_wall * 2
    else:						# 아니라면 가능한 만큼만 아래로 다녀온다
        counts['d'] += extra_moves // 2
        counts['u'] += extra_moves // 2
        extra_moves = 0
    
    # 2번 & 4번
    if extra_moves > y_wall * 2: # 여유가 있다면 벽을 찍고 돌아오고
        counts['l'] += y_wall
        counts['r'] += y_wall
        extra_moves -= y_wall * 2
    else:						# 아니라면 가능한 만큼 왼쪽으로 다녀온다
        counts['l'] += extra_moves // 2
        counts['r'] += extra_moves // 2
        extra_moves = 0

	# 3번
    if extra_moves > 0: # 그래도 여유가 있으면 rl 와리가리
        extra = 'rl' * (extra_moves // 2)

	# 빠른 순서대로 합친다
    answer = counts['d'] * 'd' + counts['l'] * 'l' + extra + counts['r'] * 'r' + counts['u'] * 'u'
    return answer

이렇게 구현해서 통과했다. 설명을 돕기 위해 코드에 주석을 달았다.

백트래킹

위의 DFS 코드에서 move의 길이를 count에 memoize해 시간을 조금이나마 줄이고 push와 escape 조건을 보완해 백트래킹으로도 해결할 수 있었다. (이게 의도된 정석 풀이 방식 같긴 하다)

import sys
sys.setrecursionlimit(10 ** 6)

from collections import deque

def getDistance(x, y, r, c):
    return abs(r - x) + abs(c - y)

def solution(n, m, x, y, r, c, k):
    DIRECTIONS = ['d', 'l', 'r', 'u']
    dx, dy = [1, 0, 0, -1], [0, -1, 1, 0]
    
    stack = deque([])
    stack.append([x, y, 0, ''])
    
    while stack:
        cx, cy, count, move = stack.pop()
        
        if cx == r and cy == c:
            if count == k:
                return move
            elif (k - count) % 2 == 1:
                return 'impossible'
        
        temp = []
        
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 < nx <= n and 0 < ny <= m and getDistance(nx, ny, r, c) + count + 1 <= k:
                temp.append([nx, ny, count + 1, move + DIRECTIONS[i]])
        
        temp.reverse()
        stack += temp
    
    return 'impossible'