[프로그래머스] 거리두기 확인하기 (Javascript, 2021 카카오 채용연계형 인턴십)

문제 링크

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

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

 

풀이

간단한 BFS 문제입니다. 각 사람마다 BFS를 돌리는데, 'O'이면 진행 가능하고 'X'이면 진행 불가능합니다.

깊이 최대 2까지의 모든 자리를 확인하여 주변에 사람이 있는지 체크합시다.

 

알아둬야 할 점이 있습니다.

자바스크립트의 배열이 앞쪽으로 넣고 빼는 unshift(), shift() 연산을 지원하긴 하지만 시간 복잡도가 O(N)으로 상당히 느립니다.

이렇게 범위가 작은 문제에서는 배열을 Queue처럼 써도 상관없습니다. 만약 큐에 들어가고 나오는 원소들이 많아지는 경우엔 다른 방법으로 큐를 구현하셔야 함을 알려드립니다.

 

 

정답 코드

const n = 5;
const d = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const isValidPos = (x, y) => (0 <= x && x < n && 0 <= y && y < n);
const isCorona = (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[0];
            q.shift();
            d.forEach(v => {
                const [nx, ny] = [x + v[0], y + v[1]];
                if (!isValidPos(nx, ny) || chk[nx][ny] || place[nx][ny] === 'X') return;
                q.push([nx, ny]);
                chk[nx][ny] = true;
            });
        }
        const ret = q.reduce((ret, [x, y]) => (place[x][y] === 'P') || ret, false);
        if(ret) return ret;
    }
    
    return false;
}

const go = (ans, place) => {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (place[i][j] === 'P' && isCorona(place, i, j)) {
                ans.push(0);
                return ans;
            }
        }
    }

    ans.push(1);
    return ans;
}

function solution(places) {
    return places.reduce(go, []);
}