[프로그래머스 Level 2] 거리두기 확인하기 - JavaScript

문제 링크

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

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

풀이

function solution(places) {
    const result = [];
    const offsetX = [0, 0, -1, 1];
    const offsetY = [-1, 1, 0, 0];
    
    const bfs = (start, place) => {
        const visited = [...Array(5)].map(() => Array(5).fill(false));
        const queue = [start];
        while (queue.length) {
            const [x, y, depth] = queue.shift();
            if (!visited[x][y]) {
                visited[x][y] = true;
                
                if (depth && place[x][y] === 'P') {
                    return false;
                }
                offsetX.forEach((dx, i) => {
                    const newX = x + dx;
                    const newY = y + offsetY[i];
                    if (newX >= 0 && newX < 5 && newY >= 0 && newY < 5
                        && depth < 2 && place[newX][newY] !== 'X') {
                        queue.push([newX, newY, depth + 1]);
                    }
                });
            }
        }
        return true;
    };
    
    places.forEach(place => {
        let hasDistance = 1;
        outer: for (let i = 0; i < 5; i++) {
            for (let j = 0; j < 5; j++) {
                if (place[i][j] === 'P' && !bfs([i, j, 0], place)) {
                    hasDistance = 0;
                    break outer;
                }
            }
        }
        result.push(hasDistance);
    });
    
    return result;
}

각 대기실별로 모든 자리를 순회하면서 응시자가 있는 자리마다 BFS로 맨해튼 거리 2까지의 자리를 탐색하여 거리두기를 잘 지키고 있는지 확인한다.

 

BFS를 할 때에는 큐에 [x, y, depth]의 형식으로 현재 자리의 위치와 응시자와의 거리를 담는다. 응시자와의 거리가 2까지인 자리까지만 탐색을 하여 만약 한 번이라도 다른 응시자가 거리 2 내에서 발견된다면 그 즉시 false를 반환하고 탐색을 종료하고, 해당 대기실의 순회를 중단하게 된다.

모든 응시자가 거리두기를 잘 지키고 있다면 모두 true를 반환할 것이다.

 

최종적으로 false를 한 번이라도 반환했던 대기실은 0, 모두 true를 반환한 대기실은 1로 배열에 담아서 반환하면 된다.