[프로그래머스] 2023 KAKAO BLIND RECRUITMENT - 미로 탈출 명령(Lv.3)

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150365

 

문제 요약

• (x, y) 위치에서 시작해, (r, c) 위치까지 정확히 k번 이동해서 도달해야 한다.
• 이동 방향은 'd', 'l', 'r', 'u' 네 가지.
• 이동 가능한 경로 중 사전순으로 가장 빠른 문자열을 출력.
• 불가능하면 "impossible"을 출력.

처음엔 DFS로..

처음에는 DFS로 모든 경로를 다 탐색하면서
(x, y) → (r, c)로 도달할 수 있는 경로를 전부 모아서
그 중 사전순으로 가장 빠른 걸 고르면 되겠다고 생각했다.

실제로 그렇게 짰고, 로직도 잘 돌아가는 듯 보였다.
하지만 결과는...

❌ 시간초과, 런타임에러

이유는 간단!
이 문제는 도달할 수 있는 경로가 너무 많고,
k번 안에 끝내야 하는 제약조건도 있어서
가지를 제대로 치지 않으면  풀 수 없는 문제였다.

 

 

개선된 풀이 – BFS + break

그래서 BFS로 탐색을 하되,
각 위치에서 'd', 'l', 'r', 'u' 순서대로 확인하면서,
조건을 만족하는 첫 번째 방향만 큐에 넣고 바로 break를 걸었다.

이게 왜 되느냐면?

어차피 정답 하나만 출력할 거고,
그게 사전순으로 가장 빠른 거 하나면 되기 때문이다.

즉, 사전순 가장 앞선 방향이 가능하다면,
나머지 방향은 더 이상 볼 필요조차 없다.

 

from collections import deque

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

    def is_possible(cur_x, cur_y, count):

        distance = abs(r-cur_x) + abs(c-cur_y)

        return (k-count) >= distance  and (k - count - distance) % 2 == 0

    directions_ch = ['d', 'l', 'r', 'u']

    directions = [(1,0), (0,-1), (0, 1), (-1, 0)]

    found = False

    queue = deque()

    queue.append((x,y,0,''))

    while queue:

        x, y, cnt, letter = queue.popleft()

        if not is_possible(x,y,cnt) or cnt > k:

            continue

        if (x,y) == (r,c) and cnt == k:

            return letter

        for ch, (dx, dy) in zip(directions_ch, directions):

            nx, ny = x + dx, y + dy

            if 1 <= nx <= n and 1 <= ny <= m:

                if is_possible(nx, ny, cnt+1):

                    queue.append((nx, ny, cnt+1, letter+ch))

                    break

    return 'impossible'