[프로그래머스] Level2 - 거리두기 확인하기(Javascript)

프로그래머스

▶ 문제 요약

1. 다음과 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있다. 

2. 대기실은 5개이며, 각 대기실은 5x5 크기이다.

3. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.

4. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용한다. 

5. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 리턴하도록 함수를 완성해라.

 

▶ 정답 코드

function solution(places) {
    let answer = [];
    // 입력값을 for of 구문으로 해당 배열을 bfs 함수에 넣어준다. 
    for (let i of places) {
        answer.push(bfs(i))
    }    
    return answer;
}


function bfs(p) {
    
    let start = [];
    
    // 응시자가 앉아있는 자리를 찾고 그 위치를 배열에 담는다.
    for (let i = 0; i < 5; i++) {
        for (let j = 0; j < 5; j++) {
            if (p[i][j] === "P") {
                start.push([i, j]);
            }
        }
    }
    
    // 응시자의 자리를 돌면서
    for (let s of start) {
        let queue = [];
        // queue에 넣어주고
        queue.push(s);
        
        // 방문표시와, 거리를 담을 배열을 만든다. 
        let visited = Array.from(Array(5), () => Array(5).fill(0));
        let distance = Array.from(Array(5), () => Array(5).fill(0));
        
        // 시작 방문 표시한다. 
        visited[s[0]][s[1]] = 1;
        
        // queue가 있을때까지
        while (queue.length > 0) {
            // 큐를 빼주고 
            let [x, y] = queue.shift();
            
            // 사방탐색
            const dx = [-1, 0, 0, 1];
            const dy = [0, -1, 1, 0];
            
            // 사방탐색 시작
            for (let i = 0; i < 4; i++) {
                let nx = x + dx[i];
                let ny = y + dy[i];
                
                // 범위가 벗어나지 않는지
                if (nx > -1 && nx < 5 && ny > -1 && ny < 5 && visited[nx][ny] === 0) {
                    // 빈테이블인 경우 탐색 가능하다
                    if (p[nx][ny] === "O"){
                        // 큐에 다음 탐색할 방향을 넣어주고
                        queue.push([nx, ny]);
                        // 방문표시한다.
                        visited[nx][ny] = 1;
                        // 거리도 갱신한다. 
                        distance[nx][ny] = distance[x][y] + 1;   
                    }
                    // 만약 또 다른 응시자를 만나고 현재 거리가 2 미만이면 거리두기가 되지 않는다. 
                    if (p[nx][ny] === "P" && distance[x][y] <= 1) {
                        // 0을 return 
                        return 0;
                    }
                }
                
            }
        }
    }
    // 1을 return
    return 1;
    
}

▶ 풀이 과정

1. 정답을 구하는 함수와 bfs 함수 두 개의 함수를 활용했다. 

 

2. bfs 함수에서 가장 먼저 할 일은 거리두기가 잘 되어있는지를 파악하는 것이 이 문제에 핵심이니까 응시자가 앉아 있는 자리를 찾고 그 위치를 배열에 담는다. 이중 for문을 사용해서 P를 찾아서 배열에 담으면 된다. 

 

3. 응시자의 자리의 위치를 담은 배열을 돌아주면서 queue에 위치를 넣어준다. 

 

4. 방문했던 곳을 재방문하지 않고, 거리두기가 잘 되고 있는지 거리를 측정하기 위한 두 개의 배열이 5*5크기만큼 필요하다. 

 

5. queue가 있을 때까지 while문을 돌면서 탐색을 위해서 큐에서 현재 탐색할 방향을 빼준다.

 

6. 사방탐색을 위한 배열이 필요하고 사방탐색을 시작하면서 범위가 벗어나지 않는지 그리고 방문한 적이 없는지를 확인한다. 

 

7. 빈 테이블인 경우에는 탐색이 가능하니 다음 방향으로 가기 위해서 큐에 탐색할 방향을 넣어주고 방문표시, 거리 갱신을 한다. 

 

8. 만약 다른 응시자를 만났을 때 현재의 거리가 2 미만이라면 거리두기가 되지 않기 때문에 0을 담고 아니면 1을 담는다. 

 

9. 정답 함수에서 주어진 입력값을 for of 구문을 활용해서 bfs 함수에 인자로 넣어줘서 돌리고 리턴되는 값을 정답 배열에 넣어준다.