[python] (프로그래머스) 미로 탈출 명령어

대회명/문제출처: 프로그래머스- 2023 KAKAO BLIND RECRUITMENT
https://school.programmers.co.kr/learn/courses/30/lessons/150365
유형: DFS

<풀이방법>

1) DFS로 풀어야한다. 

2) 모든 경로를 탐색하는 것이 아니라, 몇몇의 예외를 지정해서 break를 해야한다.

• 사전 순서로 출력하기 때문에, 애초에 경로를 사전 순서대로 하여 Greedy 방법으로 풀어야한다.
• 현재 위치에서 목적지까지 남은 최소 거리와 현재까지 이동한 거리가 k보다 크면 안되고, 또한 홀수만큼 남으면 안된다.

 

원래는 DFS로만 풀다가, 시간초과가 자꾸 뜨길래,,,,, 힌트를 참고하여서 풀이하였다. 

 

def solution(n, m, x, y, r, c, k):
    answer = 'impossible'

    stack=[[x,y,'',0]] #[[x,y],s,distance]
    dx=[1,0,0,-1]
    dy=[0,-1,1,0]

    while stack:
    	cx,cy,cs,cd=stack.pop()
    	if (cx,cy)==(r,c) and cd==k: return cs
    	if (cx,cy)==(r,c) and (k-cd)%2==1: continue
    	if abs(cx-r)+abs(cy-c)+cd>k: continue
    	for d in range(4):
    		nx=cx+dx[d]
    		ny=cy+dy[d]
    		nd=cd+1
	    	if nx<=0 or nx>n or ny<=0 or ny>m: continue
    		if nd+abs(nx-r)+abs(ny-c)>k: continue

    		if d==0:
    			ns=cs+'d'
    		elif d==1:
    			ns=cs+'l'
    		elif d==2:
    			ns=cs+'r'
    		else:
    			ns=cs+'u'
    		stack.append([nx,ny,ns,nd])
    		break



    return answer