(프로그래머스 Lv.2) 거리두기 확인하기 - 자바스크립트
2022.06.20
지금부터 코딩테스트를 연습하며 괜찮았던 문제들을 포스팅해 보려고 합니다. 한 번에 많은 시간을 할애하지는 못하지만, 꾸준히 공부하며 알고리즘 카테고리를 채워나가 보겠습니다. 🥰.
🤔 문제 설명
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리뤄 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있다.
- 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
- 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
- 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
😲 참고
자세한 사항은 프로그래머스 공식사이트에서 확인할 수 있다. 프로그래머스-거리두기 확인
💡 코드
function solution(places) {
const answer = [];
const MOVE = [
[0, -1],
[0, 1],
[1, 0],
[-1, 0],
];
const SIZE = 5;
//유효성 검사
const isValid = (x, y) => x >= 0 && y >= 0 && x < SIZE && y < SIZE;
const isAvailableSeat = (x, y, checked) => {
if (isValid(x, y) && checked[x][y] === 0) return true;
return false;
};
//BFS
const BFS = (start, room, checked) => {
let queue = [start];
while (queue.length > 0) {
const [x, y, n] = queue.shift();
if (n !== 0 && room[x][y] === 'P') return false;
MOVE.forEach(([mx, my]) => {
const _x = x + mx;
const _y = y + my;
if (isAvailableSeat(_x, _y, checked) && room[_x][_y] !== 'X') {
if (n < 2) {
checked[_x][_y] = 1;
queue.push([_x, _y, n + 1]);
}
}
});
}
return true;
};
const checkDistancing = (room) => {
let checked = Array.from({ length: SIZE }, () => Array(SIZE).fill(0));
for (let i = 0; i < SIZE; i++) {
for (let j = 0; j < SIZE; j++) {
if (room[i][j] !== 'P') continue;
checked[i][j] = 1;
if (!BFS([i, j, 0], room, checked)) return 0;
}
}
return 1;
};
return places.map(checkDistancing);
}
📝 풀이
이 문제는 거리 2 이내에 다른 사람이 있는 정점이 있는지를 검사하면 되는 문제이다. 그렇다면 DFS, BFS로 풀 수 있을 거 같다. 이번에는 BFS로 풀어 보겠다.
const checkDistancing = (room) => {
let checked = Array.from({ length: SIZE }, () => Array(SIZE).fill(0));
for (let i = 0; i < SIZE; i++) {
for (let j = 0; j < SIZE; j++) {
if (room[i][j] !== 'P') continue;
checked[i][j] = 1;
if (!BFS([i, j, 0], room, checked)) return 0;
}
}
return 1;
};
-
checkDistancing
은 이중 for문을 사용하여places
에서P
를 찾아BFS()
함수에 넣어주는 함수이다. -
checked[i][j]
는 BFS탐색 시 방문 여부를 체크해주기 위해서 사용하였다.
//BFS
const BFS = (start, room, checked) => {
let queue = [start];
while (queue.length > 0) {
const [x, y, n] = queue.shift();
if (n !== 0 && room[x][y] === 'P') return false;
MOVE.forEach(([mx, my]) => {
const _x = x + mx;
const _y = y + my;
if (isAvailableSeat(_x, _y, checked) && room[_x][_y] !== 'X') {
if (n < 2) {
checked[_x][_y] = 1;
queue.push([_x, _y, n + 1]);
}
}
});
}
return true;
};
-
bfs 탐색을 위한
queue
를 만들고 시작점을 넣어준다. -
탐색 중 다른
P
를 만나면 바로false
를 리턴하여 반복문을 빠져나온다. 시작점은 항상P
이기 때문에n !== 0
조건을 추가하였다. -
시작점에서 상,하,좌,우를 탐색한다.
//유효성 검사
const isValid = (x, y) => x >= 0 && y >= 0 && x < SIZE && y < SIZE;
const isAvailableSeat = (x, y, checked) => {
if (isValid(x, y) && checked[x][y] === 0) return true;
return false;
};
-
범위를 벗어나지 않고, 아직 방문하지 않은 곳이면서 방문 표시를 하고
queue
에 넣어준다. -
queue
가 비워지고 반복문을 통과했다면, 거리두기를 준수했다는 의미이므로true
를 리턴한다.
궁금하신 점이 있다면 아래 댓글
로 남겨주세요!👇