[프로그래머스] 2023 KAKAO BLIND RECRUITMENT - 미로 탈출 명령어

문제

프로그래머스

---

핵심

전형적인 미로찾기 문제이다. 단순히 dfs 또는 bfs를 떠올려 문제 풀면 쉽게 풀렸을 문제였다.

심지어 이 문제는 미로에서 별다른 벽이 존재하지 않아 최단거리는 명확하게 주어진 문제였다. 이게 오히려 나한텐 독이 됐을까?

굳이 dfs나 bfs를 쓸 필요가 없다고 생각해서 요상한 방법으로 풀려다가 실패했다... (근데 이 방법도 잘했으면 더 좋은 결과가 나왔던 것 같다..!)

 

1. 이 문제에서는 dfs가 적절하다.

 그 이유는 우선순위가 정해져 있고, 우선 순위 방향으로 먼저 도달하는 경우만 고려하는 방식이 더 효율적이기 때문이다.

 

2. dfs로 탐색을 하다가 탐색을 멈춰야 하는 경우

  - 현재 위치로 부터 목적지까지 최소 이동거리가 남아 있는 이동 횟수보다 클 때.

  - 남아 있는 이동 횟수가 홀수일 때

  - 현재 위치의 row 값이 0이하 또는 n 초과일 때

  - 현재 위치의 col 값이 0이하 또는 m 초과일 때

 

dfs로 탐색하고 위 조건이 걸렸을 때만 탐색을 멈춰주면 쉽게 풀리는 문제였다.

---

코드

# 불가능한 경우
# 1. k가 최소 이동거리보다 짧을 때
# 2. k - 최소 이동거리가 홀수일 때

# 신경써야되는 부분
# 1. 사전적으로 앞에 있더라도 범위를 벗어나는 부분
# 2. 사전순 d,l,r,u

def solution(n, m, x, y, r, c, k):
    words = ['u', 'r', 'l', 'd']
    dx = [-1, 0, 0, 1]
    dy = [0, 1, -1, 0]

    if checkPreCondition(x, y, r, c, k):
        return "impossible"

    stack = [(x, y, [], 0)]

    while stack:
        curR, curC, curPath, curK = stack.pop()

        if curK == k and curR == r and curC == c:
            return ''.join(curPath)

        for i in range(4):
            postR = curR + dx[i]
            postC = curC + dy[i]
            postK = curK + 1
            if 0 < postR <= n and 0 < postC <= m and postK <= k and not checkPreCondition(postR, postC, r, c, k - postK):
                q.append((postR, postC, curPath + [words[i]], postK))

    return "impossible"


def checkPreCondition(x, y, r, c, k):
    min_distance = abs(x - r) + abs(y - c)
    return k < min_distance or (k - min_distance) % 2 == 1

---

문제점

1. 그래프 탐색이면 그래프 탐색 알고리즘부터 떠올려서 해결하자. 이게 익숙해진 이후에 좀 더 효율적인 알고리즘을 고민해도 늦지 않다.

 

2. 방향을 설정해서 움직여야할 경우 dx, dy 방식을 사용하자

 

3. 그래도 조건들은 잘 찾아낸 것 같아서 뿌듯하다.