프로그래머스: 미로 탈출 명령어 - javascript(dfs 그래프, 맨해튼 거리)

문제 출처 

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

프로그래머스

 

정답 풀이 

DFS 알고리즘을 활용해서 미로에서 탈출하는 경로를 찾는 문제. 

- k번의 이동 

- 사전순으로 가장 빠른 경로 반환 

 

1. 맨해튼 거리 계산 

- 출발점에서 목표점까지의 맨해튼 거리 계산 

- 만약, k이동 횟수가 이 거리보다 작거나, 맨해튼 거리와 k의 홀짝성이 다르면 도달 할 수 없으므로 => impossible 

 

2. dfs 

- 스택을 사용하여 dfs 구현 

- 후입선출방식, 현재 위치에서 이동 가능한 모든 방향 탐색 

- 방향은 사전 순으로 빠른 d,l,r,u 순으로 탐색 

 

3. 경로 탐색 및 유효성 검사 

- 현재 위치에서 목표 위치까지 남은 이동 횟수로 도달 가능한지 판단 

- 만약 경로가 k만큼의 길이를 가지면서 목표점에 정확히 도달하면 그 경로 반환 

- 탐색 도중 유효하지 않거나 더이상 탐색할 필요 없는 경로는 가지치기 

 

 정답 코드 

 

난 못풀겠어서, 이 분의 코드로 학습하고, 조금은 수정했다. 

출처 

https://medium.com/@songforthemute/programmers-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-lv-3-%EB%AF%B8%EB%A1%9C-%ED%83%88%EC%B6%9C-%EB%AA%85%EB%A0%B9%EC%96%B4-c1525241a469

Programmers. | 프로그래머스 Lv.3 미로 탈출 명령어

 

function solution(n, m, x, y, r, c, k) {
    
    if(!isAbleToArrive(k,x-1,y-1,r-1,c-1)) return "impossible"
    
    const stack = [[x-1,y-1, '']]
    
    while(stack.length){
        const [curX, curY, acc] = stack.pop()
        
        if(isAbleToArrive(k-acc.length,curX, curY, r-1,c-1)){
            if(isArrive(curX, curY, r-1, c-1)){
                if(k === acc.length) return acc 
                if(curX < n-1) stack.push([curX+1, curY, acc + 'd'])
                if(curY > 0) stack.push([curX, curY-1, acc + 'l'])
                if(curY < m-1) stack.push([curX, curY+1, acc + 'r'])
                if(curX > 0) stack.push([curX-1, curY, acc + 'u'])
                
            }
           for(let [nx, ny, nacc] of getDirs(curX, curY, acc)){
               if(isValid(n,m,nx,ny)) stack.push([nx, ny, nacc])
           }
        }
    }
    return "impossible"
}

const getManhattan = (x,y,r,c) => Math.abs(x-r) + Math.abs(y-c)

const isAbleToArrive = (k,x,y,r,c) => k >= getManhattan(x,y,r,c) && getManhattan(x,y,r,c)%2 === k%2

const isArrive = (x,y,r,c) => x === r && y === c

const isValid = (n,m,x,y) => x >= 0 && y >= 0 && x < n && y < m

const getDirs = (x, y, acc) => [
    [x-1, y, acc+'u'],
    [x, y+1, acc+'r'],
    [x, y-1, acc+'l'],
    [x+1, y, acc+'d'],
]