[Programmers] 미로 탈출 명령어 (미완)

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

 

내 풀이

# (x, y)에서 (r, c)로 이동해 탈출해야 함
# 미로 탈출 조건
    # 격자 밖으로 못나감
    # 이동거리 총 k
    # 같은 격자 두 번 이상 방문 가능
    # 문자열이 사전 순으로 가장 빠른 경로로 탈출
# dfs (최단거리 아니라 k거리)

def solution(n, m, x, y, r, c, k):
    answer = []

    
    # r, l, d, u 동서남북
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    shortest = abs(r-x)+abs(c-y)
    if (k < shortest) or ((k-shortest)%2 == 1):
        return "impossible"
    
    def dfs(xx, yy, num, journey):
        if num == k:
            if (k-shortest)%2 == 1:
                answer.append("impossible")
                return
            if xx == r and yy == c: #k거리만에 목적지 도착
                answer.append(journey)
                return
            else:
                return
        
        for i in range(4):
            nx, ny = xx+dx[i], yy+dy[i]
            if 0 < nx <= n and 0 < ny <= m:
                if i == 0:
                    dfs(nx, ny, num+1, journey+'r')
                elif i == 1:
                    dfs(nx, ny, num+1, journey+'l')
                elif i == 2:
                    dfs(nx, ny, num+1, journey+'d')
                else:
                    dfs(nx, ny, num+1, journey+'u')
            
    dfs(x, y, 0, '')
    if len(answer) == 0:
        return "impossible"
    if answer[-1] == "impossible":
        return "impossible"
    answer.sort()
    return answer[0]

틀렸는데, 정확히 어디가 틀린지 아직 못 찾았다.

 

우선 이 문제의 핵심은 "탈출할 수 없는 경우"를 처리해주는 것이었다.

1. k가 최단거리(dist)보다 작을 때

2. 도착했는데, (걸린 거리 - k)%2가 1일 때

 

참고할 풀이들

https://cheon2308.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv3-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%AF%B8%EB%A1%9C-%ED%83%88%EC%B6%9C-%EB%AA%85%EB%A0%B9%EC%96%B4

[프로그래머스 Lv3] 파이썬 - 미로 탈출 명령어

https://velog.io/@chocochip/2023-KAKAO-BLIND-RECRUITMENT-%EB%AF%B8%EB%A1%9C-%ED%83%88%EC%B6%9C-%EB%AA%85%EB%A0%B9%EC%96%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%AC%B8%EC%A0%9C-%EB%B0%8F-%ED%92%80%EC%9D%B4

2023 KAKAO BLIND RECRUITMENT - 미로 탈출 명령어 (파이썬) 문제 및 풀이