[탐색] 미로 탈출 명령어 ( 파이썬 )

문제 설명

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

프로그래머스

문제 풀이

• 방문했던 곳을 다시 가는 것이 허용되는 문제이므로 방문을 최소화하면서 최적의 길을 찾아야 함
• 방향 ( down,up, left,right ) 에 대해 알파벳 순서는 d, l, r, u이다.
• 방문을 최소화 하기 위해 최소 힙을 사용함. 
• 알파벳 순서는  dlru 이므로 이것을 반대로 뒤집은 u, r, l d 로 탐색을 진행하면서 각 dist에 (-1 * dir) 을 더할 것
• 아래는 continue 조건 들
  • 그리고 어떤 좌표에 있을 때, (그 좌표에서부터 도착 지점까지의 거리 + 지금까지 이동한 횟수) >k 일 경우 어떤 방법을 가더라도 그 좌표에서는 도착 지점을 성립 할 수 없으므로 continue 처리
  • gr[n+1][m+1] = 0 그래프를 만들어서 탐색 중인 방식(dist - dir ) 이 gr[x][y] 보다 값이 클 경우 continue 처리
• 아래는 해당 코드

소스 코드

import heapq

dx = [-1,0,0,1]
dy = [0,-1,1,0]
dy = [0,1,-1,0]
d = ['u', 'r', 'l', 'd']

def solution(n, m, sx, sy, ex, ey, k):
    answer = []
    q = []
    gr = [[0]*(m+1) for i in range(n+1)]
    heapq.heappush(q,(0,0,sx,sy,[]))
    while(q):
        dist, cnt, x, y,dir = heapq.heappop(q)
        if cnt==k and [x,y]==[ex,ey]:
            answer=dir
            break
        if cnt+abs(ex-x)+abs(ey-y)>k:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            cd = d[i]
            if nx<=0 or ny<=0 or nx>n or ny>m:
                continue
            if dist-i-1>gr[nx][ny]:
                continue
            gr[nx][ny]=dist-i-1
            heapq.heappush(q,(dist-i,cnt+1,nx,ny,dir+[cd]))
    

    return "".join(answer) if answer else "impossible"

print(solution(3, 4, 2, 3, 3, 1, 5))

 

오답 노트

1. 탐색 중인 횟수 + (현재 좌표~끝 좌표 거리) >k 이면 아웃이라고 지정 => 시간 초과
2. visited [n,m,k] 를 만들어서 visited[nx][ny][cnt] 가 방문했다면 아웃이라고 가정 => 1보다는 괜찮은 시간 초과
3. heapq를 만들어서 d = [ 'u', 'r', 'l', 'd' ] 를 만든 뒤 0,-1,-2,-3 을 둬서 우선 순위로 방문 시킴. 알파벳 순서는 dlru니까 반대로 해서 마이너스 값 주고 최소힙 쓴것 => 테스트 31에서 시간 초과 
   • 방문 그래프를 따로 둬서 현재의 탐색 방식의 계산 값(방향들 더한 값) 방문 그래프에 저장된 숫자보다 크다면 continue를 해줬더니 성공

import heapq

dx = [1,0,0,-1]
dy = [0,-1,1,0]
# 하 좌 우 상
d = ['d', 'l', 'r', 'u']

def solution(n, m, sx, sy, ex, ey, k):
    answer = []
    
    visited = [[[[] for z in range(k+1)] for i in range(m+1) ] for j in range(n+1)] # 이것도 시간 초과 요소
    q = []
    heapq.heappush(q,(0,0,sx,sy))
    
    while(q):
        dist, cnt, x, y = heapq.heappop(q)
        if cnt==k and [x,y]==[ex,ey]:
            answer=visited[x][y][cnt]
            break
        if cnt>=k:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            cd = d[i]
            if nx<=0 or ny<=0 or nx>n or ny>m:
                continue
            if visited[nx][ny][cnt+1]!=[]:
                continue
            visited[nx][ny][cnt+1]=visited[x][y][cnt]+[cd]
            heapq.heappush(q,(dist+i+1,cnt+1,nx,ny))
    

    return "".join(answer) if answer else "impossible"

print(solution(3, 4, 2, 3, 3, 1, 5))