[프로그래머스] 미로탈출 명령어

링크

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

프로그래머스

문제풀이

한칸씩 움직이는 것을 보고 dfs, bfs를 떠올릴 수 있었다.

하지만 평소 접하던 문제와의 차이점은 다음과 같다.

• 같은 곳을 여러번 움직일 수 있다는 것
• 사전순으로 가장 앞에 오는 경우를 return 시킬 것

처음에 풀었던 방식은 기존의 bfs처럼 풀었다. 

1. queue 배열 생성, 첫 인자로 [시작점 x, 시작점 y, 정답이 될 string, 움직인 횟수 count]
2. q  배열을 돌면서 시작점과 끝점이 동일하고 count가 k값과 같으면 answer 배열에 정답을 담는다.
3. answer 배열의 길이가 0 이면 impossible 반환, 아닐 경우 sort를 통해 첫번째 값을 반환한다.

다음의 방법은 시간초과가 발생하여서 당연스럽게 문제를 풀지 못했다.

시간초과를 줄일 수 있는 부분에 대해서 생각을 해보자

먼저

같은 곳을 여러번 움직일 수 있다는 것

같은 곳을 여러번 움직일 수 없는경우엔 visited 배열을 만들어 이미 방문한 곳은 다시 가지 않듯이 움직일 필요가 없는 경우를 배제하자.

배제하는 경우에 대해서 생각해보면

• 도착지까지 최소거리가 움직일 수 있는 수보다 클 때

사전순으로 가장 앞에 오는 경우를 return 시킬 것

• 사전순으로 가기 때문에 내가 움직일 수 있는 경우 다른 상황은 고려하지 않는다. 좀 더 구체적으로 설명하자면 다음 움직일 수 있는 상황이 down, left, right, up  순으로 방문할 수 있는지 알아보는데 만약 down방향으로 움직일 수 있다면 left right, up은 더 고려하지 않아도 된다는 것이다.
  위의 방법으로 코드를 짜게 되면 방금전에 sort + 배열의 첫 인덱스를 return 시키는 방식이 아니라 제일 먼저 도착한 것이 사전순으로도 제일 빠르게 되어 정답이 된다.

from collections import deque

# 최소거리 구하는 함수
def distance(x, y, r, c):
    return abs(x - r) + abs(y - c)

def solution(n, m, x, y, r, c, k):
    answer = ''
    move = [(1, 0), (0, -1), (0, 1), (-1, 0)]
    move_directions = ['d', 'l', 'r', 'u']
    q = deque([(x, y, 0, '')])
    
    dist = distance(x, y, r, c)
    
    if k < dist or (k - dist) % 2 == 1:
        return 'impossible'
    
    while q:
        i, j, cnt, s = q.popleft()
        # k가 최소거리 보다 작은경우, k - 최소거리가 홀수인 경우 무조건 도달할 수 없다.
        # 예시 3번을 보면 k는 4이고 dist는 3임을 확인할 수 있는데 도착지에 도달한 후 한칸 움직였다가
	    # 다시 돌아오려는 경우 짝수가 아니면 돌아올 수 없어서 impossible이 된다.
        if i == r and j == c:
            if cnt == k:
                return s
            elif (k - cnt) % 2:
                return 'impossible'
        for idx, v in enumerate(move):
            ii = i + v[0]
            jj = j + v[1]
            # 움직일 수 있는 거리 < 최소거리 인 경우 pass
            if k < cnt + distance(ii,jj,r,c):
                continue
            if 1 <= ii <= n and 1 <= jj <= m:
                q.append((ii, jj, cnt + 1, s + move_directions[idx]))
                # 시간초과 회피, 사전순 정답 도출을 위해 q에 append 되면 다음 move는 신경쓰지 않는
                break 
                    
    return 'impossible'

 

q.append 다음 break 한줄 때문에 몇 시간을 헤맸다.