[알고리즘] - 미로 탈출 명령어 (2023 카카오 공채)

• 이번 문제는 미로 탈출 명령어 입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

TC 추가해보기

• 문제를 이해하기 위해, Test Case를 추가해봤습니다.

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

• S가 시작 지점, E가 끝 지점이라고 했을 때, 위와 같은 격자 상태에서 k를 7로 설정했습니다.
• 즉, 7번의 이동으로 S에서 E로 가는 경로를 구해야 합니다.
• 기본적으로 S에서 E로 가기 위해선 3번의 r 과 2번의 d 가 필수적으로 필요하고, 그 외에는 2번의 이동씩 쌍을 맞춰서 (ex 위-아래, 왼쪽-오른쪽) 다시 제자리로 돌아올 수 있도록 하면 됩니다.

• 그렇기에 rrrddud … 등 여러 조합이 가능하지만 그 중 사전 순으로 가장 빠른 조합은 ddrlrrr 이 됩니다.

• output : ‘ddrlrrr’

접근 방식

• 위의 TC를 추가하는 과정에서 떠올린 아이디어를 이용하여 크게 두 단계로 문제에 접근했습니다.
  1. S -> E로 가는 최단 경로에 필요한 문자열을 구한 뒤, 리스트에 저장하기
  2. 해당 리스트의 사이즈를 n이라고 할 때 k-n 만큼은 2번의 이동씩 쌍을 맞춰서 제자리로 돌아올 수 있도록 문자 쌍을 리스트에 추가한 뒤, 이를 사전 순으로 사용하기
• 자세한 구현 과정은 아래의 코드와 함께 설명해보겠습니다.

구현

• 먼저 x와 r, y와 c의 차이를 활용해서 두 지점 사이의 이동을 위해 반드시 필요한 문자열들을 리스트에 저장합니다.
  • 만약 문자열 리스트의 크기가 k보다 크거나, 혹은 문자열 리스트의 크기를 n이라고 했을 때 k-n % 2 != 0 이라면 k번 안에 (r,c)로 이동할 수 없음으로 impossible을 리턴합니다.
• d > l > r > u 순서로 문자를 반복합니다.
  • 현재 문자가 의미하는 위치로의 이동이 격자 범위를 벗어나지는 않는지 체크합니다.
  • 만약 이동 가능한 위치라면, 기존의 문자열 리스트에서 현재 문자가 있는지 확인하고 있다면 이를 사용합니다. (answer에 추가한 뒤 문자열 리스트에서 제거합니다.)
    • 문자열 리스트에서 현재 문자가 없다면, k와 (현재 문자열 리스트의 사이즈 + 지금까지 문자열 리스트에서 제거한 문자의 개수) 간의 차이를 확인한 뒤, 이 차이가 2보다 크거나 같다면, 현재 문자를 answer에 추가해준 뒤(사용한 뒤), 현재 문자의 반대 방향의 문자를 문자열 리스트에 추가합니다.
• 위의 과정을 k만큼 이동할 때까지 반복합니다.

# Programmers 150365, 미로 탈출 명령어
def solution(n, m, x, y, r, c, k):
    answer = ''
    queue = []

    # r, c로 가는데 필요한 문자열 찾기
    if r - x > 0:
        for _ in range(r - x):
            queue.append('d')
    elif r - x < 0:
        for _ in range(x - r):
            queue.append('u')

    if c - y > 0:
        for _ in range(c - y):
            queue.append('r')
    elif c - y < 0:
        for _ in range(y - c):
            queue.append('l')

    # queue의 크기가 k보다 크거나, k에서 queue의 사이즈만큼 뺀 것이 2의 배수가 아니라면 출력 후 종료
    size = len(queue)
    if size > k or (k - size) % 2 != 0:
        return "impossible"

    # queue를 사전 역순으로 정렬
    queue.sort(reverse=True)

    template = ['d', 'l', 'r', 'u']
    step = [(1, 0), (0, -1), (0, 1), (-1, 0)]

    limit = 0
    while limit < k:
        limit += 1

        for i, elem in enumerate(template):

            # 경계선을 넘어가는지 체크
            mv_x, mv_y = x + step[i][0], y + step[i][1]
            if mv_x <= 0 or mv_x > n or mv_y <= 0 or mv_y > m:
                continue

            # 만약 이미 queue가 비었다면, 해당 문자와 반대 방향의 문자를 넣고 진행
            if not queue:
                queue.append(rev_dir(elem))
                queue.append(elem)

            # 해당 문자가 사용 가능하다면, 사용 후 이동
            if queue[-1] == elem:
                answer += queue.pop()
                x, y = mv_x, mv_y
                break
            # 해당 문자가 사용 불가하다면
            else:
                # k - (queue사이즈 + limit)가 2보다 크거나 같은지 확인
                if k - (len(queue) + limit - 1) >= 2:
                    # 해당 문자를 사용한 셈치고, 반대 급부를 사용할 queue에 추가
                    answer += elem
                    queue.append(rev_dir(elem))
                    # queue 재정렬
                    queue.sort(reverse=True)
                    x, y = mv_x, mv_y
                    break

                # 2보다 작다면, 더이상 추가할 수 없음으로 그냥 continue
                continue

    return answer

def rev_dir(elem):
    if elem == 'u':
        return 'd'
    elif elem == 'd':
        return 'u'
    elif elem == 'r':
        return 'l'
    else:
        return 'r'

• 중간에 queue가 비었는지 확인하는 이유는, 로직이 실행되는 과정에서 k만큼 이동하지 않았음에도 queue가 비었을 때를 대비하기 위함입니다.

Review

문제를 이해하는 과정에서 Test Case를 추가해봤는데, 이 덕분에 문제에 대해서 더 빠르게 이해할 수 있었던 것 같습니다. 또한 절반 이상의 시간을 로직을 구상하는데 쓴 덕분인지 구현 과정에서는 크게 흔들리지 않았던 것 같습니다. 다만 문제 풀이 방식을 다시 적으면서 보니 굉장히 장황하다는 느낌이 많이 들었습니다. 조금 더 간결하고 명확한 알고리즘을 짤 수 있도록 연습해야 할 것 같습니다.