문제 링크

프로그래머스 문제

풀이

첫시도는 dfs로 풀었다.

1. d -> l -> r -> u 순서로 정렬
2. k보다 클때 종료
3. dist에 따른 종료 시점 확인

하지만 이와 같은 방식이라면 bfs로도 풀 수 있지 않을까?

코드

function solution(n, m, x, y, r, c, k) {

    const [startX, startY] = [x,y];
    const [targetX, targetY] = [r,c];
    const move = [[1,0],[0,-1],[0,1] , [-1,0] ] // 아래로, 오른쪽으로, 위로, 좌측으로
    const dir = ["d","l","r","u"]
    let answer = "z".repeat(k);
   
    if(k < Math.abs(startX - targetX) + Math.abs(startY - targetY) ){
        return "impossible"
    }
    if((k - Math.abs(startX - targetX) + Math.abs(startY - targetY)) % 2 !== 0){
        return "impossible"
    }
    
    const checkLocation = (x,y) => {
        if(1 <= x && x <=n && 1 <= y && y <=m){
            return true
        }else return false
    }
    let isArrived = false;
    
    
    
    const dfs = (curX, curY, curCount , curString , dist) => {
        // 종료 조건
        if(curCount > k){
            return;
        }
        
       
        
        if(dist > k) return;
        
        
        if(curCount === k && curY === targetY && curX === targetX){
            isArrived = true;
                answer= curString
                return
        }
        // 다음 조건
        if (isArrived) return; // 이게 중요한 역할을 수행하는 것으로 보임
        
        for(let i=0; i < 4; i++){
            const [dx, dy] = move[i]
            const [nextX, nextY] = [curX + dx, curY+dy]
            const curDir = dir[i]
            if(checkLocation(nextX , nextY)){
                dfs(nextX , nextY, curCount+1, curString+ curDir , Math.abs(nextX - targetX) + Math.abs(nextY- targetY) + curCount+1) // 가장 중요한 부분
            }
        }
        
        
    }
    dfs(startX , startY, 0, "" , k)
    return answer.length >0 ? answer : "impossible";
}
// 방향에 있어서 좌측상단은 1,1이고 우측 하단은 3,4이다. 
// 숫자가 증가하면 우측 , 아래로 이동하는 것이다. 
// 도착해야만 한다. 
// visited 여부가 중요한가? 아니다
// 시작지점과 도착지점 모두 중복하여 도착해도 괜찮습니다.