프로그래머스 거리두기 확인하기 JavaScript

2022년 12월 26일

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

제한 사항

places의 행 길이(대기실 개수) = 5
- places의 각 행은 하나의 대기실 구조를 나타냅니다.
places의 열 길이(대기실 세로 길이) = 5
places의 원소는 P,O,X로 이루어진 문자열입니다.
- places 원소의 길이(대기실 가로 길이) = 5
- P는 응시자가 앉아있는 자리를 의미합니다.
- O는 빈 테이블을 의미합니다.
- X는 파티션을 의미합니다.
입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
return 값 형식
- 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
- places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
- 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

풀이

queue를 이용한 BFS로 풀이했다.
우선 대기실 별 응시자가 앉아있는 자리 'P'의 좌표만을 저장한다.
대기실은 5x5 크기로 고정이기 때문에 예제의 다섯 번째 대기실인 경우가 응시자가 앉을 수 있는 자리의 최대의 경우이다.(최대 응시자 수 = 13) 따라서 'P'의 개수가 13 보다 클 경우 거리두기를 지킬 수 없기에 push 0 을 한다.

단 한 번이라도 거리두기 실패 시 그 대기실은 거리두기를 지킬 수 없기에 대기실을 빠져나가기 위해 하나의 대기실을 탐색하는 for문에 label: block을 선언한다.
이후 왔던 길을 돌아가지 않기 위한 배열 ch를 선언한 후, 대기실의 인덱스를 넘어가지 않고, 거리가 2보다 작고 이동할 위치에 places 가 'O' 인 경우에만 이동할 좌표를 queue에 push (2보다 작은 거리 안에서 'P'를 만날 경우 거리두기 실패로 해당 대기실 반복문을 나와준다.)
또한 'P'와 다른 'P' 사이의 대각선에 'X'가 두개 다 있는 경우 'P'를 만날 수 없기에 상하좌우 방향만 BFS 한다.

check가 true인 경우 거리두기 실패로 push 0, false인 경우에는 성공으로 push 1을 한다.

solution.js

class Queue {
    constructor() {
      this._arr = [];
    }
    enqueue(item) {
      this._arr.push(item);
    }
    dequeue() {
      return this._arr.shift();
    }
}

function solution(places) {
    let answer = [];
    const userXY = new Array(5);
    const directX = [-1, 0, 1, 0];
    const directY = [0, 1, 0, -1];

    for(let i = 0; i < 5; i++) {
        const room = places[i]
        userXY[i] = new Array();
        for (let gx = 0; gx < 5; gx++) {
            for (let gy = 0; gy < 5; gy++) {
                if (room[gx][gy] == 'P') {
                    userXY[i].push([gx, gy]);                 
                }
            }
        }
    }
    
    for (let i = 0; i < 5; i++) {
        if (userXY[i].length > 13) {
            answer.push(0);
            continue
        }
        const queue = new Queue();
        let check = false;
        const XY = userXY[i];
        
block: for (let j = 0; j < XY.length; j++) {
            const x = XY[j][0];
            const y = XY[j][1];
            ch = Array.from(Array(5), () => new Array(5));
            ch[x][y] = 1
            queue.enqueue([x,y])

            while (queue._arr.length !== 0) {
                const temp = queue.dequeue();
                const tx = temp[0];
                const ty = temp[1];

                for (let d = 0; d < 4; d++) {
                    const dx = directX[d]+tx;
                    const dy = directY[d]+ty;
                    if (0 <= dx && dx < 5 && 0 <= dy && dy < 5 && (Math.abs(dx-x) + Math.abs(dy-y) <= 2) && ch[dx][dy] !== 1) {
                        if (places[i][dx][dy] === 'O'){
                            ch[dx][dy] = 1;
                            queue.enqueue([dx,dy]);
                        }
                        else if (places[i][dx][dy] === 'P'){
                            check = true;
                            break block;
                        }
                    }s
                }
            }
        }
        check === true ? answer.push(0) : answer.push(1);
    }
    return answer;
}

프로그래머스 거리두기 확인하기 JavaScript

제한 사항

풀이

댓글