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

※ 사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

프로그래머스

---

 

문제접근

◇ 미로의 x, y에서 시작하여 r, c로 이동하여 탈출하는 문제이다. 탈출할 때 주의 해야 하는 조건은 다음과 같다.

1. 격자 밖으로 나갈 수 없다. 

2. x,y 에서 r, c로 이동한 거리가 총 "k" 여야 한다.

3. 경로를 문자열로 나열했을 때 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 한다.

 

◇ 조건들로 인해 생기는 특이 케이스를 하나씩 살펴본다면 다음과 같다.

- 2번 조건에 의해, 현재 좌표(cx, cy)에서 도착지 좌표(r, c)의 남은 거리는 반드시 짝수 어야 한다. 이유는 남은 거리가 "k"보다 크다면, 도착지 좌표를 지나갈 수밖에 없고, 지나간 곳에 되돌아오기 위해서는 다른 곳에 갔다 다시 도착지로 돌아오는, "왕복" 이동을 해야 한다. 왕복 이동은 남은 거리가 짝수일 때만 가능하기 때문에, 남은 거리는 반드시 짝수 어야 한다.

- 3번 조건에 의해 사전 순에 맞춰 움직이도록 설정해야 한다. 즉, 사전순으로 가장 빠른 "d", 아래로 가는 움직임이 먼저 나타나고 그다음에 왼쪽(l)으로 움직이게 만들어준다.

 

◇ 효율성 테스트의 기준이 빡빡함으로 최대한 탐색을 진행하지 않을 수 있다면 진행하지 않도록 막아주는 것이 문제의 또 다른 핵심 포인트다.

---

 

문제풀이 (With Python)

import sys

sys.setrecursionlimit(10**6)

command = ["d","l","r","u"]
dx = [1, 0, 0, -1]
dy = [0, -1, 1, 0]

def checking(n,m, cx, cy, r, c, k, dist, path):
    global flag
    if flag or abs(cx-r) + abs(cy-c) + dist > k:
        return

    if dist == k and cx == r and cy == c:
        flag = True
        answer.append(path)
        return

    for i in range(4):
        nx = cx + dx[i]
        ny = cy + dy[i]
        # idx가 1부터 시작
        if 0 < nx <= n and 0 < ny <= m:
            checking(n,m, nx, ny, r, c, k, dist+1, path+command[i])
            
answer = []
flag = False

def solution(n, m, x, y, r, c, k):
    global answer

    remain = k - abs(x-r) + abs(y-c)
    if remain < 0 or remain % 2 != 0:
        return "impossible"

    checking(n, m, x, y, r, c, k, 0, "")

    if answer:
        return answer[0]
    else:
        return "impossible"

 

◇  flag 변수는 도착지에 도착한 빠른 경로를 찾았다면, 더는 탐색을 진행하지 않고 멈추게 만든다.

(이때 flag를 global로 선언한 이유는 일반 지역변수로 선언하게 되면 재귀 안의 flag와 재귀 밖의 flag가 다른 변수로 설정되기 때문에 flag가 제대로 동작하지 않는다.)

 

◇ checking 함수 안에서 남은 이동거리가 "k" 보다 크면 탐색을 멈춘다.