카테고리 없음

99클럽 코테 스터디 7일차 TIL

난쟁이 개발자 2024. 4. 19. 19:11
반응형

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

문제 링크

성능 요약

메모리: 10.3 MB, 시간: 0.00 ms

구분

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

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 04월 17일 21:59:46

문제 설명

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...

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 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
입출력 예
n m x y r c k result
3 4 2 3 3 1 5 "dllrl"
2 2 1 1 2 2 2 "dr"
3 3 1 2 3 3 4 "impossible"
입출력 예 설명

입출력 예 #1

문제 예시와 동일합니다.

입출력 예 #2

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

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

S.
.E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (2, 2)입니다.

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

  1. rd
  2. dr

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

입출력 예 #3

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

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

.S.
...
..E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 3)입니다.

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

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

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

 

풀이 - DFS

더보기 
import sys
sys.setrecursionlimit(10**8)

# down, left, right, up 알파벳 순으로 정렬
dx = [1, 0, 0, -1]
dy = [0, -1, 1, 0]
dAlpha = ['d', 'l', 'r', 'u']
answer = "z"    # 가능한 경로중 사전 순으로 가장 앞서는 경로를 저장. 초기값 z으로 설정하여 모든 문자열보다 뒤에 오도록 함

# isValid 함수는 주어진 위치가 n*m 격자 안에 있는지 확인
def isValid(nx, ny, n, m) :
    return 1 <= nx <= n and 1 <= ny <= m

# dfs함수는 깊이 우선 탐색을 통해 가능한 모든 경로를 찾는다.
def dfs(n, m, x, y, r, c, prev_s, cnt, k) :
    global answer
    # 현재 위치에서 목표 위치까지의 최소 이동 횟수보다 남은 이동 가능 횟수가 적을 경우 탐색 종료
    if k < cnt + abs(x - r) + abs(y - c) :
        return
    # 목표 위치에 도달했고 이동 횟수가 정확히 k일 때, 경로를 업데이트
    if x == r and y == c and cnt == k :
        answer = prev_s
        return
    # down, left, right, up  이동시도
    for i in range(4) :
        # 다음 위치가 유효하고 현재 경로가 지금까지의 최적해보다 사전순으로 앞서면 탐색 계속
        if isValid(x+dx[i], y+dy[i], n, m) and prev_s < answer :
            dfs(n, m, x+dx[i], y+dy[i], r, c, prev_s + dAlpha[i], cnt + 1, k)

def solution(n, m, x, y, r, c, k):
    # 맨해튼 거리 계산
    distance = abs(x - r) + abs(y - c)
    # 맨해튼 거리가 k보다 크거나, k와 거리의 차이가 홀수일 경우, 도착할 수 없으므로
    if distance > k or (k - distance) % 2 == 1 :
        return "impossible"
    dfs(n, m, x, y, r, c, "", 0, k)
    return answer

 

풀이 - 수학

더보기 
def solution(n, m, x, y, r, c, k):
    diff = abs(x - r) + abs(y - c)
    # 목표까지의 거리가 k와 같은 홀수/짝수여야 하며, k가 더 커야 함
    if diff % 2 != k % 2 or diff > k :
        return "impossible"
    
    rest = k - diff  # 남은 이동 횟수
    lcnt = rcnt = dcnt = ucnt = 0
    # x, y에서 r, c까지의 기본적인 이동 횟수 계산
    if x < r :
        dcnt = r - x
    else :
        ucnt = x - r
        
    if y < c :
        rcnt = c - y
    else :
        lcnt = y - c
    
    # 남은 이동 횟수를 최대한 활용해서 추가적인 이동 횟수를 계산
    dplus = min(n - max(x, r), rest // 2)
    rest -= dplus * 2
    
    lplus = min(min(y, c) - 1, rest // 2)
    rest -= lplus * 2
    
    # 최종 경로 문자열 생성
    answer = 'd'*(dcnt + dplus)+'l'*(lcnt + lplus)+'rl'* (rest//2)+'r'*(rcnt+lplus)+'u'*(dplus+ucnt)
    
    return answer

조건을 잘 살펴보면, 

시작점 (x, y) 로부터 목표점(r,c)까지 정확히 k번 이동하여 도달할 수 있는 경로 중 사전순으로 가장 앞서는 경로를 찾는 문제

  • dx, dy, dAlpha 배열은 상하좌우 이동을 위한 배열이며, 각각 상 하 좌 우 이동을 나타낸다. dAlpha는 이동 방향을 문자로 나타내는 배열로, 이 배열의 값들은 최종 경로 문자열을 구성하는데 사용된다. 
  • isValid 함수는 주어진 위치가 n * m 배열 안에 있는지 확인하는 함수다. 이동 가능성을 검사할 때 사용된다.
  • dfs 깊이 우선 탐색 함수. 현재 위치에서 목표 위치까지 도달할 수 있는지, 그리고 이동 횟수가 정확히 k인지 검사한다. 조건을 만족하면 answer를 업데이트 한다. 이 함수는 모든 상하좌우 방향으로 재귀적으로 자신을 호출하며, 가능한 모든 경로를 탐색한다.
  • solution : 시작점에서 목표점까지의 맨해튼 거리를 계산하고, 이 거리가 k보다 크거나 k와 거리의 차이가 홀수일 경우 "impossible"을 반환한다. 그렇지 않을 경우, dfs함수를 호출하여 가능한 경로를 탐색하고, 최적의 경로를 반환한다.
  1. 맨해튼 거리를 이용한 필터링 : 시작점에서 목표점까지의 맨해튼 거리가 k보다 크거나, k와 거리의 차이가 홀수인 경우, 문제의 조건을 만족하는 경로는 존재할 수 없다. 이는 최소 이동 횟수를 만족하지 않거나, 홀/짝수 이동 횟수의 불일치 때문이다
  2. DFS : 가능한 모든 경로를 탐색하여 조건을 만족하는 최적의 경로를 찾아낸다. 재귀적으로 모든 방향을 탐색하며, 유효한 이동만을 수행한다. 탐색 과정에서 사전 순으로 더 앞서는 경로를 발견할 경우, answer를 업데이트한다.

챌린저 문제를 해결하면서 구현 시뮬레이션 등을 많이 연습해오고 있지만, 아직까지 많은 어려움이 있다. 그리고 아이디어를 떠올리는데 있어 많은 시행착오가 필요하다고 생각한다. 

반응형