프로그래머스 - 게임 맵 최단거리 (JS)

프로그래머스 2레벨도 제대로 못 푸는데(생각해보니 1레벨도 못 풀면서)
3레벨 푼다고 까불었다가 도망쳐왔다.

아이템 줍기 라는 DFS/BFS 3레벨 문제 풀어본다고 패기있게 들어갔는데, 문제 처음 대충 봤을 때는 아! BFS로 가면 되겠다. 하고 열심히 코드 짰는데 외곽선 카운트를 어떻게 해야하는지 몰라서 혼자 고민하다가 아무리 생각해도 모르겠어서 구글링해봤더니 사람들이 맵을 2배로 키워서 풀고 있었다. 호곡..ㅜㅜ 이게뭐람.
결국 난이도를 낮춰서 풀고 나중에 레벨업 해서 풀어야겠다..ㅜㅜ하는 생각으로 2레벨 문제부터 풀어보기로 했다.

비슷한 유형인 DFS/BFS 문제 게임 맵 최단 거리 문제를 골랐다.
문제 보자마자 BFS가 좋겠다고 생각했다.
근데 이 문제는.. 와.. 3레벨 문제 보다가 왔더니 천사인가? 하고 좋아했는데
일단 처음 제출하자마자 정확성은 다 맞았는데 효율성에서 0점 ㅋㅋㅋㅋ 아니 ㅋㅋ 왜요 ㅠ

어쩐지 문제 보자마자 기분이 좋더라.. 그럼 그렇지~
효율성에서 또..........

/* 효율성 0점 받은 풀이 */
function solution(maps) {
    let result = 0;
    const visited = Array(maps.length).fill(0).map(()=> Array(maps[0].length).fill(0))
    const dy = [1, 0, -1, 0];
    const dx = [0, 1, 0, -1];
    const q = [];
    q.push([0, 0]);
    visited[0][0] = 1;
    
    while(q.length){
       const [y, x] = q.shift();
        
        for(let i = 0; i < 4; i++){
            let ny = y + dy[i];
            let nx = x + dx[i];
            
            if(ny < 0 || nx < 0 || ny >= maps.length || nx >= maps[0].length || maps[ny][nx] === 0 ) continue;
            if(visited[ny][nx]) continue;
            q.push([ny, nx]);
            visited[ny][nx] = visited[y][x] + 1;
        }
    }
    
    
    result = visited[maps.length - 1][maps[0].length - 1];
    
    if(!result) return -1;
    return result;
}

애초에 못가면 앞에서 -1을 리턴시켜버려야 효율성 테스트에서 통과할 수 있을 것 같았다.
문제에서 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치 라고 했기 때문에

그렇다면 도착지점은 항상 고정되어 있고, 우측 하단이라는 점을 고려하면
도착 지점을 기준으로 1칸 위와 1칸 왼쪽만 체크하면 된다는 의미라고 해석했다.

/* 통과한 코드 */

function solution(maps) {
    let result = 0;
    const visited = Array(maps.length).fill(0).map(()=> Array(maps[0].length).fill(0))
    const dy = [1, 0, -1, 0];
    const dx = [0, 1, 0, -1];
    const q = [];
    q.push([0, 0]);
    visited[0][0] = 1;
    
    if(maps[maps.length - 1][maps[0].length - 2] === 0 && maps[maps.length - 2][maps[0].length - 1] === 0) return -1;
    
    while(q.length){
       const [y, x] = q.shift();
        
        for(let i = 0; i < 4; i++){
            let ny = y + dy[i];
            let nx = x + dx[i];
            
            if(ny < 0 || nx < 0 || ny >= maps.length || nx >= maps[0].length || maps[ny][nx] === 0 ) continue;
            if(visited[ny][nx]) continue;
            q.push([ny, nx]);
            visited[ny][nx] = visited[y][x] + 1;
        }
    }
    
    result = visited[maps.length - 1][maps[0].length - 1];
    
    if(!result) return -1;
    return result;
}

어쩐일로 금방 푸는 문제가 있다니 뿌듯뿌듯
자바스크립트로 알고리즘 사이트에 있는 DFS/BFS 문제 푸는건 처음이라 더 좋당 🥰