[Programmers] 거리두기 확인하기 (Lv 2, JavaScript)

[ 개요 ]
풀이시간 : 92분

[ 학습 내용 ]
간단한 bfs로 진행했으나, JS에서 4방향 처리에 대해 고민해봐야겠다.

var d = [{"x":0, "y":1},{"x":0, "y":-1},{"x":1, "y":0},{"x":-1, "y":0}]

다음처럼 처리하였으나, 2차원 배열로 선언하는게 덜 귀찮을것 같음

[ 소스 코드 ]

function solution(places) {
    var answer = [];
    var peoples;
    answer = places.map((place) => {
        peoples = [];
        place.forEach((line, index) => {
            var tables = line.split("");
            tables.forEach((table, idx) => {
                if(table === "P") {
                    peoples.push({"x":idx, "y":index});
                }
            })  
        })
        
        var d = [{"x":0, "y":1},{"x":0, "y":-1},{"x":1, "y":0},{"x":-1, "y":0}]
        const range = (y, x) => {
            return y<0 || x<0 || y>4 || x>4 || place[y][x] === "X";
        }
        
        for(var i=0; i<peoples.length; i++) {
            var visit = Array.from(new Array(5), () => Array(5).fill(false))
            let queue = [];
            let p = peoples[i];
            p.cnt = 0;
            queue.push(p);
            visit[p.y][p.x] = true;
            do {
                let out = queue.shift();
                if (out.cnt >= 1 && out.cnt <= 2) {
                    if (place[out.y][out.x] === "P") {
                        return 0;
                    }
                }
                if (out.cnt === 2) continue;
                for(var k=0; k<4; k++) {
                    let ny = out.y + d[k].y;
                    let nx = out.x + d[k].x;
                    let nc = out.cnt + 1;
                    if (!range(ny, nx) && !visit[ny][nx]) {
                        visit[ny][nx] = true;
                        queue.push({"x": nx, "y":ny, "cnt": nc});
                    }
                }
            } while(queue.length != 0)
        }
        return 1;
    })
    
    return answer;
}

[ 코드 분석 ]

다음과같이 맨해튼의 거리가 2이하인 경우를 찾고, 1인경우는 배제하여 바로 0을 리턴하였고 2인경우에 BFS를 진행하였으나 테케 11번을 해결할 수 없었다.

결국 모든 P에 대해 BFS를 진행하여 해결하였다.

var flag = false;
var distancing = peoples.map((r, index) => {
    for(var i=index+1; i<peoples.length; i++) {
        let c = peoples[i];
        let manhattan = Math.abs(r.y - c.y) + Math.abs(r.x - c.x);
        if (manhattan <= 2) {
            if (manhattan === 2) return r;
            flag = true;
        }
    }
}).filter(dist => dist !== undefined)

if (flag) return 0;