99클럽 코테 스터디 6일차 TIL (미로 탈출 명령어)

---

99클럽 코테 스터디

단순 구현으로 평이한 편이었다.

1번 문제 미로 탈출 명령어 : https://school.programmers.co.kr/learn/courses/30/lessons/150365

출처 : 프로그래머스

---

1번 문제 미로 탈출 명령어

---

풀이 접근

조건 파악 + 구현 문제이다.

start와 end 간의 가로 좌표 차이 + 세로 좌표 차이가 k보다 크거나 k와 홀짝성이 다르면 impossible

이외엔 다 가능하니 사전순으로 가장 앞에 오는 탈출로를 반환하면 된다.

풀기만 하면 문제가 쉬운 편이라, 최대한 효율적으로 탈출로를 빌드하도록 했다.

탈출로를 빌드하는 과정은 다음과 같다. (사전 순은 d(아래) > l(왼쪽) > r(오른쪽) > u(위쪽)이다.)

1. 내려갈 수 있는 만큼 최대한(도착점에 딱 맞춰 도달할 수 있을 만큼 or 맨 아래까지) 내려간다. (dd 이런식)
2. 왼쪽으로 갈 수 있을 만큼 최대한 간다. (ddlll 이런식)
3. 아직도 도착점까지 남은 거리보다 이동해야 할 남은 거리가 많은 경우(=현재 미로의 맨 왼쪽 밑이라는 얘기이다), 오른쪽-왼쪽을 반복해서 도착점까지 남은 거리를 남은 이동 횟수에 맞춘다. (ddlllrlrl 이런식)
4. 도착점에 최단거리로 오른쪽 전부 + 위쪽 전부만큼 이동해서 도착한다. (ddlllrlrlrru 이런식)

괄호 안에 있는 예시는 아래 그림의 예시와 같다.
남은 거리가 계속 여유로우므로,
1. 맨 아래까지 이동하고(사전순 가장 앞인 d로 최대한 채우기),
2. 맨 왼쪽까지 이동하고(그 다음인 l로 채우기),
3. 우좌 반복(rl)과 상하(ud) 반복중 사전순으로 더 앞인 우좌 반복으로 남은 이동 거리를 줄이고,
4. 남은 이동은 반드시 r과 u이므로 r부터 다쓰고 u를 쓰는 것이다.

물론, 남은 이동 거리가 얼마나 여유있느냐에 따라 1~4의 과정 중 실제로는 이동하지 않는 과정이 있을 수 있음에 유의한다.

---

코드 (Python3, 통과, 최대 0.01ms, 10.5MB)

2500칸짜리 벽 없는 미로에서 이동해 봤자이긴 하지만, 문자열을 빌드해서 반환하는 것 치고 0.01ms면 만족스러운 최적화라고 생각한다.

down은 시작 위치(또는 현재 위치)에서 도착점까지 세로 좌표 차이(내려가는 게 양수)이다.
left는 시작 위치(또는 현재 위치)에서 도착점까지 가로 좌표 차이(왼쪽으로 가는 게 양수)이다.
down_wall은 시작 위치(또는 현재 위치)에서 맨 아래까지 남은 세로 거리이다.
left_wall은 시작 위치(또는 현재 위치)에서 맨 왼쪽까지 남은 가로 거리이다.

k는 총 이동 거리로 주어지지만, 이동할 때마다 이동한 만큼 빼 주면서 남은 이동 거리로 활용했다. 마찬가지로 x,y 좌표도 시작 좌표로 주어지지만, 이동할 때마다 갱신해서 현재 위치 좌표로 바꿔주었다. 이동할 때마다 down과 left도 값을 갱신해 주었다.

go_down, go_left, go_right_and_left는 위 풀이에서 탈출로를 빌드하는 과정 1~3에 각각 해당하는 이동 횟수이다.

변수를 제대로 갱신했다면, 4번 과정은 -left만큼 오른쪽으로, -down만큼 위로 이동하는 과정이 된다.

def solution(n, m, x, y, r, c, k):
    # d l r u 아래 왼 오른 위
    answer = ''
    down = r - x
    left = y - c
    down_wall = n - x
    left_wall = y - 1
    if k < abs(down)+abs(left) or (k-down-left)%2:
        answer = 'impossible'
        return answer
    if down > 0:
        answer += 'd' * down
        k -= down
        down = 0
        x = r
        down_wall = n - x
    go_down = min((k - abs(down) - abs(left))//2, down_wall)
    answer += 'd' * go_down
    k -= go_down
    x += go_down
    down = r - x
    if left > 0:
        answer += 'l' * left
        k -= left
        left = 0
        y = c
        left_wall = y - 1
    go_left = min((k - abs(down) - abs(left))//2, left_wall)
    answer += 'l' * go_left
    k -= go_left
    y -= go_left
    left = y - c
    go_right_and_left = (k - abs(down) - abs(left))//2
    answer += 'rl' * go_right_and_left
    answer += 'r' * -left
    answer += 'u' * -down
    
    return answer