[프로그래머스] 거리두기 확인하기 (Lv 2) - javascript

📝 문제

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

 

• 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
• 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
• 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

문제 더보기

 

🔑 모범 풀이

 

풀이 과정

P가 있는 위치에서 별로 둘러싸인 마름모 부분을 검색하면 거리두기 성공 여부를 알 수 있다.

주의할 점은 탐색할 위치가 좌표를 벗어나지 않게 처리해야 한다는 것이다.

 

P의 사방에 있는 하늘색 o 부분을 탐색

1. x면 넘어간다.

2. P면 거리두기 실패

3. O로 비어있으면 => 다시 O의 사방(P를 제외한 별부분)을 탐색

  3-1. P가 있다면 실패

 

구현

function solution(places) {
    let answer = [];
    
    places.forEach(place => {
        answer.push(roomCheck(place));
    })
    
    return answer;
}

function roomCheck(place) {

    let queue = [];
    
    for(let r = 0; r < 5; r++) {
        for(let c = 0; c < 5; c++) {
            if(place[r][c] === 'P') queue.push([r,c]);
        }
    }
    
    while(queue.length) {
        
        let [x,y] = queue.shift();
        let moveX = [-1,1,0,0];
        let moveY = [0,0,-1,1];

        for(let i = 0; i < 4; i++) {
            let nx = x + moveX[i];
            let ny = y + moveY[i];
           
            if(nx < 0 || nx > 4 || ny < 0 || ny > 4) continue;
            if(place[nx][ny] === 'P') return 0;
            if(place[nx][ny] === 'X') continue;
            
            if(place[nx][ny] === 'O') {
                for(let j = 0; j < 4; j++) {
                    let aroundnx = nx + moveX[j];
                    let aroundny = ny + moveY[j];
                    if(aroundnx < 0 || aroundnx > 4 || aroundny < 0 || aroundny > 4) continue;
                    if(aroundnx === x && aroundny === y) continue;
                    if(place[aroundnx][aroundny] === 'P') return 0;
                }
            }
        }
    }
    return 1;
}

 

• 구현 풀이

function solution(places) { // 각 대기실 순회하며 거리두기 여부 체크해서 answer에 추가
    let answer = [];
    
    places.forEach(place => {
        answer.push(roomCheck(place));
    })
    
    return answer;
}

function roomCheck(place) { // 거리두기 여부 반환 함수 

    let queue = [];
    
    for(let r = 0; r < 5; r++) {
        for(let c = 0; c < 5; c++) {
            if(place[r][c] === 'P') queue.push([r,c]); // P가 있는 좌표를 큐에 추가
        }
    }
    
    while(queue.length) {
        
        let [x,y] = queue.shift();
        let moveX = [-1,1,0,0];
        let moveY = [0,0,-1,1];

        for(let i = 0; i < 4; i++) { // P의 사방 순회
            let nx = x + moveX[i]; 
            let ny = y + moveY[i];
           
            if(nx < 0 || nx > 4 || ny < 0 || ny > 4) continue; // 사방이 좌표를 벗어나면 건너뛰기
            if(place[nx][ny] === 'P') return 0; // 사방 중에 P가 있으면 => 실패
            if(place[nx][ny] === 'X') continue; // X면 그 주변은 P가 있어도 거리두기 되니까 건너뛰기
            
            if(place[nx][ny] === 'O') { // 만약 비어있다면
                for(let j = 0; j < 4; j++) { // 그 부분의 사방을 다시 탐색
                    let aroundnx = nx + moveX[j];
                    let aroundny = ny + moveY[j];
                    if(aroundnx < 0 || aroundnx > 4 || aroundny < 0 || aroundny > 4) continue; // 좌표 벗어나는지 체크
                    if(aroundnx === x && aroundny === y) continue; // P랑 겹치면 건너뛰기
                    if(place[aroundnx][aroundny] === 'P') return 0; // 만약 P가 있다면 => 실패
                }
            }
        }
    }
    return 1; // 이 험난한 과정을 모두 지나쳤다면 => 성공!
}

문제를 읽어도 결과를 도출하는 로직을 짜는 것이 정말 어려운 것 같다.

해당 풀이는 아래 참고 블로그의 풀이를 내 방식대로 약간 수정한 것이다.

 

• 정확도 테스트 결과

 

---

참고

velog.io/@hsk10271/