[level 3] 미로 탈출 명령어 - 150365

문제 링크

성능 요약

메모리: 9.39 MB, 시간: 8.33 ms

구분

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동
• r: 오른쪽으로 한 칸 이동
• u: 위쪽으로 한 칸 이동
• d: 아래쪽으로 한 칸 이동

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

1. lldud
2. ulldd
3. rdlll
4. dllrl
5. dllud
6. ...

이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

제한사항

• 2 ≤ n (= 미로의 세로 길이) ≤ 50
• 2 ≤ m (= 미로의 가로 길이) ≤ 50
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• 1 ≤ r ≤ n
• 1 ≤ c ≤ m
• (x, y) ≠ (r, c)
• 1 ≤ k ≤ 2,500

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 동일합니다.

입출력 예 #2

미로의 크기는 2 x 2입니다. 출발 지점은 (1, 1)이고, 탈출 지점은 (2, 2)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

S.
.E

탈출까지 이동해야 하는 거리 k가 2이므로 다음과 같은 경로로 탈출할 수 있습니다.

1. rd
2. dr

"dr"이 사전 순으로 가장 빠른 경로입니다. 따라서 "dr"을 return 해야 합니다.

입출력 예 #3

미로의 크기는 3 x 3입니다. 출발 지점은 (1, 2)이고, 탈출 지점은 (3, 3)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

.S.
...
..E

탈출까지 이동해야 하는 거리 k가 4입니다. 이때, 이동 거리가 4이면서, S에서 E까지 이동할 수 있는 경로는 존재하지 않습니다.

따라서 "impossible"을 return 해야 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제 풀이

문제 분석

이 문제는 $N \times M$ 크기의 미로에서 출발지 $(x, y)$부터 도착지 $(r, c)$까지 정확히 $K$번 이동하는 경로를 찾는 문제입니다. 세 가지 주요 제약 조건이 있습니다.

1. 격자 밖으로 이동할 수 없습니다.
2. 총 이동 거리는 정확히 $K$여야 합니다.
3. 여러 경로가 있을 경우, 경로 문자열('d', 'l', 'r', 'u'로 구성)을 사전 순으로 가장 빠른 것을 선택해야 합니다.

입력은 격자 크기 $N, M$, 시작 위치 $x, y$, 도착 위치 $r, c$, 총 이동 횟수 $K$입니다. 출력은 조건을 만족하는 사전 순 최소 경로 문자열이며, 경로가 존재하지 않으면 "impossible"입니다. $K$의 최대값은 2,500으로 비교적 작지만, 사전 순 최소 경로를 찾아야 하므로 단순 BFS/DFS 대신 그리디 탐색이 필요합니다.

접근 방법

이 문제는 "사전 순 최소"라는 조건 때문에 그리디 알고리즘을 사용해야 합니다. 이동 명령의 사전 순서는 d (아래) < l (왼쪽) < r (오른쪽) < u (위) 입니다. 따라서 매 이동 시점에 이 순서대로 가능한 방향을 시도하고, 가장 먼저 선택 조건을 만족하는 방향을 택해야 합니다.

가장 중요한 접근 방식은 가능성 검증 (Pruning) 입니다. 한 칸 이동을 선택했을 때, 남은 거리 $K'$ 동안 목표 지점까지 도달할 수 있는지, 그리고 남은 이동 횟수가 정확히 $K'$가 될 수 있는지를 검증해야 합니다. 이 검증은 맨해튼 거리와 이동 횟수의 패리티(parity, 홀짝성)를 이용합니다.

1. 최소 거리 확보: 현재 위치에서 목표까지 남은 최소 맨해튼 거리 $D$가, 앞으로 남은 이동 횟수 $L = K - \text{cnt}$보다 커서는 안 됩니다 ($L \ge D$).
2. 홀짝성 조건: 최소 거리 $D$로 목표에 도달한 후 남는 여유 이동 횟수 $(L - D)$는 반드시 짝수여야 합니다. 홀수 거리가 남는다면, 한 번의 왕복 이동(예: $lr$)이 두 번의 이동을 소모하므로, 남은 이동 횟수를 정확히 소모하며 목표 지점에 멈추는 것이 불가능합니다.

이 두 조건을 만족하는지 확인하는 check 함수를 사용하여 그리디 탐색을 진행합니다.

구현 설명

1. check 함수: 이동 가능성 판단 (사전 검증)

check(n, m, x, y, r, c, k, cnt) 함수는 특정 위치 $(x, y)$에서 남은 이동 횟수 $k - cnt$ 내에 목표 $(r, c)$에 도달 가능한지 검증합니다.

• 최소 거리 계산: 현재 위치 $(x, y)$와 목표 $(r, c)$ 사이의 맨해튼 거리 least = abs(r-x) + abs(c-y)를 계산합니다.
• 격자 범위 확인: 0 < x <= n and 0 < y <= m을 통해 현재 위치가 격자 내에 있는지 확인합니다.
• 거리 및 홀짝성 조건:
  • k >= least + cnt: 총 이동 횟수 $k$가 현재까지 이동한 횟수 cnt와 앞으로 최소 이동해야 할 거리 least의 합보다 크거나 같아야 합니다.
  • ((k - least - cnt) % 2 == 0): 전체 남은 여유 이동 횟수 $k - (\text{least} + \text{cnt})$가 짝수여야 합니다. 이 조건은 정확히 $K$ 횟수를 채울 수 있는지 보장합니다.

2. 그리디 탐색 루프 (K 횟수만큼 반복)

solution 함수는 $K$번의 이동을 수행하는 루프를 돌면서 매번 사전 순으로 가장 빠른 유효한 이동을 선택합니다.

• 루프는 d, l, r, u 순서로 다음 위치를 시도합니다.
• 예를 들어 'd' (아래)로 이동을 시도하는 경우, 새로운 위치 $(x+1, y)$를 check 함수로 검증합니다.
• check 함수가 True를 반환하면, 해당 이동을 확정하고 현재 위치 $(x, y)$를 업데이트하며, 경로 문자열 answer에 해당 문자를 추가하고 다음 반복으로 넘어갑니다.

3. 예외 처리

• 만약 $K$번의 루프 중 한 단계에서 'd', 'l', 'r', 'u' 네 방향 모두 check 함수를 통과하지 못하면, 현재 위치에서 남은 횟수를 $K$에 맞춰 목표 지점에 도달하는 것이 불가능하다는 의미입니다. 이 경우 즉시 "impossible"을 반환합니다.
• $K$번의 이동이 모두 성공적으로 완료되면, 최종 경로 문자열 answer를 반환합니다.

⏱복잡도 분석

시간 복잡도: $O(K)$

• 이 코드는 총 $K$번의 이동 횟수만큼 반복합니다.
• 각 반복문 내에서는 최대 4번의 방향 시도(d, l, r, u)가 이루어집니다.
• 각 시도는 check 함수를 호출하며, check 함수 내부의 연산(절댓값, 덧셈, 나머지 연산 등)은 격자 크기와 무관하게 상수 시간 $O(1)$이 소요됩니다.
• 따라서 전체 시간 복잡도는 $O(4 \times K) = O(K)$가 됩니다. $K$가 최대 2,500이므로 매우 효율적인 시간 복잡도입니다.

공간 복잡도: $O(K)$

• 알고리즘이 사용하는 주요 저장 공간은 최종 경로를 저장하는 문자열 answer입니다. 이 문자열의 길이는 $K$입니다.
• 따라서 공간 복잡도는 $O(K)$입니다.

핵심 포인트

1. 그리디 선택 (사전 순 우선순위): 경로 문자열을 사전 순으로 최소화하기 위해 이동 방향을 'd' > 'l' > 'r' > 'u' 순서로 시도하고, 조건이 만족하는 첫 번째 방향을 즉시 선택하여 확정하는 그리디 전략을 사용합니다.
2. K 이동 조건 검증 (맨해튼 거리): 단순한 최단 거리가 아닌, 정확히 $K$번 이동해야 한다는 제약 조건을 처리하기 위해, 현재 위치에서 목표까지의 맨해튼 거리 $D$를 계산합니다. 남은 이동 횟수 $L$이 $D$보다 작아서는 안 됩니다 ($L \ge D$).
3. 홀짝성(Parity) 조건 활용: $K$ 횟수를 맞추기 위해, 남은 여유 이동 횟수 $L - D$가 반드시 짝수여야 합니다. 이를 통해 목표 지점에 도달한 후, 남은 이동 횟수를 제자리 왕복(예: $lr$ 또는 $ud$)을 통해 소모하며 최종적으로 $K$번 만에 목표에 멈출 수 있는지 여부를 효율적으로 판단합니다.

풀이 코드

def solution(n, m, x, y, r, c, k):
    answer = ''
    cnt = 0
    for i in range(k):
        print(x,y)
        if check(n,m,x+1,y,r,c,k,cnt+1):
            x+=1
            cnt += 1
            answer += 'd'
            continue
        elif check(n,m,x,y-1,r,c,k,cnt+1):
            y-=1
            cnt += 1
            answer += 'l'
            continue
        
        elif check(n,m,x,y+1,r,c,k,cnt+1):
            y+=1
            cnt += 1
            answer += 'r'
            continue

        elif check(n,m,x-1,y,r,c,k,cnt+1):
            x-=1
            cnt += 1
            answer += 'u'
            continue
        
        return "impossible"
        
    
    return answer

def check(n,m,x,y,r,c,k,cnt):
    least = abs(r-x)+abs(c-y)
    if 0<x<=n and 0<y<=m:
        if ((k-least-cnt)%2 == 0) and k >= least+cnt:
            return True
        
    return False