[프로그래머스] 거리두기 확인하기 javascript

javscript 거리두기 확인하기 문제풀이

https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

bfs로 문제를 풀었습니다.

2자리 거리까지 차이를 검사해야하기 때문에 depth를 2로 지정하고 q.length && depth-- 로 큐가 비거나 depth가 0이 될 때까지 반복문을 돌리고 내부에서 상하좌우를 확인하고 파티션이 없는 곳의 좌표를 q에 push 하고 check배열에 체크합니다.

BFS() 함수는 queue를 확인하다 응시자가 한명이라도 있으면 true를 리턴해서 start 함수에서 if문에 걸려 배열에 0을 push하게 됩니다

const d = [[0,1], [-1,0], [0,-1], [1,0]];
const n = 5;
function outRange(x,y){
    return 0<=x && x < n && 0 <= y && y < n;
}

function bfs(place, x, y){
  const chk = Array.from(Array(5), () => new Array(5).fill(false));
    const q = [];
    chk[x][y] = true;
    q.push([x, y]);
    let depth = 2;
    while (q.length && depth--) {
        let len = q.length;
        while (len--) {
            [x, y] = q.shift();
            
            d.forEach(v => {
                const [xx,yy] = v;
                const [nx, ny] = [x + xx, y + yy];
                if (!outRange(nx, ny) || chk[nx][ny] || place[nx][ny] === 'X') return;
                q.push([nx, ny]);
                chk[nx][ny] = true;
            });
        }
       const ret = q.some( ([x,y]) =>place[x][y]==='P')
        if(ret) return true;
    }
    
    return false;
}

const start = (arr, place) => {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (place[i][j] === 'P' && bfs(place, i, j)) {
                arr.push(0);
                return arr;
            }
        }
    }
 
    arr.push(1);
    return arr;
}
function solution(places) {
    return places.reduce(start,[]);
}

 

https://degurii.tistory.com/228?category=908954  블로그를 참고했습니다.