미로탈출 명령어(카카오) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

처음에 DFS로 순회하면서 d > l > r > u 순으로 탐색을 하면 되지 않을까 했는데 시간 초과 및 에러가 발생했다. dfs , bfs를 응용하여 로직을 추가해주려 했으나 뭔가 계속 엉망이 되어서 그만두고 다른 분의 코드를 참고했다. 

 

전체적인 방법은 BFS 처럼 큐를 활용하며, 이웃한 4곳의 정보를 모두 큐에 넣는 것이 아닌, d > l > r > u 순으로 탐색하며 가능한 것을 큐에 넣고 이후 방향은 pass하는 방식으로 구현했다. 또한 다음 장소를 큐에 넣을 때, 다음 장소로 마지막 지점을 갈 수 있는지 여부를 판단해서 가능한 것만 큐에 넣어주도록 했다. 구체적인 처리과정은 아래와 같다.

1. 시작점과 끝점의 맨하탄 거리를 구해서 도달할 수 있는지를 판단한다
    1.1. 맨하탄 거리가 k 보다 크거나, (맨하탄 거리-k)%2==1 이면 도달할 수 없다
    
2. 큐에 시작위치를 넣고 큐를 순회한다
    2.1. 큐에서 꺼낸 위치가 마지막 지점과 같고 (k-dist)%2==1이라면 impossible을 반환한다
    2.1. 마지막 지점과 같고 k==dist라면, 이동경로를 반환한다
    
    2.3. 현재 위치에서 다음에 이동할 위치를 선정한다( d > l > r> u 순으로 탐색)
        2.3.1. 다음위치가 범위 내에 존재하고, 맨하튼 거리+(dist+1)이 k 이하라면(도달할 수 있는 거리라면) 
              큐에 넣어주고 다음 위치로 이동한다.

 

 

코드

from collections import deque

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

	# 끝점와 임의의점의 맨하탄 거리를 구하는 함수
    def manhattan(r1,c1):
        return abs(r1-(r-1))+abs(c1-(c-1))
	
    # 맨하탄 거리가 k 이상 -> 최단 경로로도 도달할 수 없다
    # %2 ==1 -> 갔던 곳을 다시 지나도 도달할 수 없는 곳
    if manhattan(x-1,y-1)>k or (manhattan(x-1,y-1)-k)%2==1:
        return "impossible"
    
    q=deque()
    q.append((x-1,y-1,0,""))
    d={(1,0):"d",(0,-1):"l",(0,1):"r",(-1,0):"u"}
    
    while q:
        cr,cc,dist,route=q.popleft()
     	
        # 마지막 지점과 같은데, %2==1이라면 어떻게서든 갈 수 없는 장소
        if (cr,cc)==(r-1,c-1) and (k-dist)%2==1:
            return "impossible"
        elif (cr,cc)==(r-1,c-1) and dist==k: # k 와 같다면 경로를 반환
            return route
            
        # d > l > r > u  순으로 순회하며 다음 장소를 구함.
        # 다음 장소가 범위 내에 존재하고, 거리 상으로도 가능한 위치라면 큐에 넣어주고 break
        for dr,dc in d: 
            nr,nc=cr+dr,cc+dc
            if 0<=nr<n and 0<=nc<m and manhattan(nr,nc)+(dist+1)<=k:
                q.append((nr,nc,dist+1,route+d[(dr,dc)]))
                break

 

 

회고

1. 다음 이동할 장소에 대해 맨하튼 거리로 미리 도달 가능한지 여부를 판단한다. 
   도달할 수 있는 것만을 큐에 넣는다.
2. 사전형으로 최소가 되는 경로로 끝점에 도달을 하도록하고, 도달 했을때 불가능한 경우를 if문으로 처리한다
3. 거리가 k 라면 경로를 반환하도록 하고, 그렇지 않은 경우는 계속해서 큐를 순회하도록한다.