[Javascript/PGS] Lv.3 : 아이템 줍기(BFS)

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

프로그래머스

 

---

프로그래머스 레벨 3 문제이다

처음에 일부 테케가 계속 틀려서 삽질했었는데

알고보니 map 변수를 채우는 게 문제였다.... (이거 하나때문에 몇 시간을 앓음)

 

js에서는 배열 값을 직접 바꿀때 중복이 되면 뭔가 오류가 생기나보다

중복, 덮어쓰기 최대한 없도록 짜기!

 

Main Idea => 맵을 두 배로 늘려서, ㄷ자로 우회해야하는데 직행하게 되는 부분이 없도록 함

그리고 최단거리를 찾는 문제이니, BFS로 푼다!

 

 

나의 풀이

let dx = [0, 1, 0, -1];
let dy = [1, 0, -1, 0];
let map = new Array(101).fill(null).map(() => new Array(101).fill(0));  
let visited = new Array(101).fill(null).map(() => new Array(101).fill(0));

function canVisit(nx, ny) {
    if (nx < 0 || nx > 100 || ny < 0 || ny > 100) return false;
    if (map[nx][ny] !== 1) return false;
    if (visited[nx][ny] === 1) return false;
    return true;
}

function bfs(x, y, itemX, itemY) {
    let q = [[x, y, 0]];
    visited[x][y] = 1;

    while (q.length !== 0) {
        let [cx, cy, cnt] = q.shift();
        if (cx === itemX && cy === itemY) return cnt / 2;
        for (let i = 0; i < 4; ++i) {
            let nx = cx + dx[i];
            let ny = cy + dy[i];

            if (canVisit(nx, ny)) {
                q.push([nx, ny, cnt + 1]);
                visited[nx][ny] = 1;
            }
        }
    }
    return -1;
}

function solution(rectangle, characterX, characterY, itemX, itemY) {
    let answer = 0;
    let doubleRec = rectangle.map(rec => rec.map (point => point*2));
    
    doubleRec.forEach(([x1,y1,x2,y2])=>{
        for(let i=x1;i<=x2;i++){
            for(let j=y1;j<=y2;j++){
                if(i === x1 || i === x2 || j === y1 || j === y2){
                    if(map[i][j]===0){map[i][j]=1;}
                }
                else{map[i][j]=2;}
            }
        }
        
    });
    answer = bfs(characterX*2, characterY*2, itemX*2, itemY*2);
    
    return answer;
}