프로그래머스: 거리두기 확인하기 - javascript(bfs, 규칙찾기)

문제 출처 

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

프로그래머스

문제 풀이 힌트 

 

01. places 장소를 반복문을 돌면서 하나의 대기실씩 판단한다.

02. 하나의 대기실에서 사람을 'P' 사람을 찾는다. 

03. 그 사람의 '상, 하, 좌, 우' 를 살핀다.

- 만약 사람이라면 바로 `안전하지 않음`

- 만약 파티션이라면 `안전함` 

- 만약 책상이라면 그 책상 상하좌우를 한번 더 살펴봐야 함.

     만약 책상의 상하좌우에

  -- 사람이 있다면, `안전하지 않음`

  -- 파티션이 있다면, `안전함`

  -- 책상이 있다면, `안전함`

 

각 대기실마다 안전하다면 1, 안전하지 않으면 0을, result에 계속 push 한다. 

 

정답 풀이 코드 

function solution(places) {
  const result = []; 
    for(let place of places){ //하나의 대기실을 판단
        let isSafePlace = 1; //그 대기실이 안전한지 check 변수 
        
        //사람을 발견하면, 상하좌우 살필것임. 
        for(let i=0; i<5; i++){
            for(let j=0; j<5; j++){
                if(place[i][j] === 'P'){ //사람이 있다면 
                    if(!isSafe(place, i,j)){ //안전한지 체크하는 함수에 인자로 (대기실, 사람위치) 전달, 만약 안전하지 않다면 
                        isSafePlace = 0; //안전하지 않다면 변수 값 0으로 변경
                        break; //더이상 해당 대기실은 살펴볼 필요 없음. 
                    }
                }
            }
        }
        result.push(isSafePlace); //안전한지, 아닌지 체크 변수 result에 push 
    }
    return result; 
}

//안전한지 체크하는 함수 
function isSafe(place, x, y){ //매개변수로 (대기실,기준이 되는 사람 위치)
    //상하좌우 살피는 idx
    const dx = [-1,1,0,0]; 
    const dy = [0,0,-1,1]; 
    
    for(let i=0; i<4; i++){ //상하좌우 살핌 
        const nx = x + dx[i]; 
        const ny = y + dy[i]; 
        
        if(nx <0 || ny <0 || nx>=5|| ny >= 5) continue;  //대기실을 벗어난다면 제껴~
        if(place[nx][ny] === 'P') return false; //사람이 있다면 바로 안전하지 않음 return 
        else if(place[nx][ny] === 'O'){ //만약 책상이라면 그 상하좌우를 한번 더 봐야함. 
            for(let j=0; j<4; j++){
                const nnx = nx + dx[j]; 
                const nny = ny + dy[j]; 
                if(nnx <0 || nny < 0 || nnx>=5 || nny >= 5) continue; //대기실 벗어난다면 제껴~
                if(nnx === x && nny === y) continue; //이건 사람이지만 기준이 되는 사람이잖아. 그러니, 제껴~ 
                if(place[nnx][nny] === 'P') return false; //만약 사람을 발견했다? return 안전하지 않음
            }
        }
    }
    return true; // 그 이외는 안전함 !
}

 

Only 풀이 코드 

function solution(places) {
  const result = []; 
    for(let place of places){
        let isSafePlace = 1; 
        
        for(let i=0; i<5; i++){
            for(let j=0; j<5; j++){
                if(place[i][j] === 'P'){
                    if(!isSafe(place, i,j)){
                        isSafePlace = 0; 
                        break; 
                    }
                }
            }
            if(!isSafePlace){
                break; 
            }
        }
        result.push(isSafePlace); 
    }
    return result; 
}

function isSafe(place, x, y){
    const dx = [-1,1,0,0]; 
    const dy = [0,0,-1,1]; 
    
    for(let i=0; i<4; i++){
        const nx = x + dx[i]; 
        const ny = y + dy[i]; 
        
        if(nx <0 || ny <0 || nx>=5|| ny >= 5) continue; 
        if(place[nx][ny] === 'P') return false; 
        else if(place[nx][ny] === 'O'){
            for(let j=0; j<4; j++){
                const nnx = nx + dx[j]; 
                const nny = ny + dy[j]; 
                if(nnx <0 || nny < 0 || nnx>=5 || nny >= 5) continue; 
                if(nnx === x && nny === y) continue; 
                if(place[nnx][nny] === 'P') return false; 
            }
        }
    }
    return true; 
}

 

나의 틀린 풀이 코드 (시간 초과남) 

function solution(places) {
    let answer = Array.from({length: 5}, () => 0);
    const dx = [-1,1,0,0]; 
    const dy = [0,0,-1,1]; 
    function bfs(y,x, graph){
        const queue = []; 
        queue.push([x,y]); 
        while(queue.length){
            for(let i=0; i<4; i++){
                let nx = x + dx[i]
                let ny = y + dy[i]; 
                if(nx <0 || ny <0 || nx >=5 || ny>= 5) continue; 
                if(graph[ny][nx] === 'P') return 0; 
                if(graph[ny][nx] === 'O'){
                    bfs(ny, nx, graph)
                }
            }
        }
        return 1 
    }
    for(let place of places){
        let graph = Array.from({length:5}, () => []); 
        for(let i=0; i<5; i++){
           graph[i] = place[i].split('')
        }
        for(let i=0; i<5; i++){
            for(let j=0; j<5; j++){
                if(graph[i][j] === 'P'){
                   let result = bfs(i,j, graph) //return 1 or 0 
                   answer.push(result)
                }
            }
        }
    }
        return answer; 
}
//거리두기 
//대기실은 5개, 크기는 5 x 5 
//거리두기는 맨해튼 거리가 2이하로 앉으면 안됨 
// - 단, 응시자가 앉아있는 자리 사이가 파티션 끼면 ㄱㅊ음. 
//=>
//응시자 P 
//빈 테이블 O 
//파티션 X
//
//각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 

//bfs로 한칸 
// - 사람 => 바로 false
// - 파티션 => 지나침 
// - 책상 => 그 기준으로 bfs 한번더 
//bfs로 두칸 
// - 사람 => false; 
// - 책상이나 파티션이면 ㄱㅊ
//bfs로 세칸은 안해도 됨. 

//places 반복문 
//- 해당 place 를 2차원 배열로 나타낸다. 
//- place에서 P를 수색하고 찾아내면, 
//- bfs로 탐색 
//- 거리두기 무사히 했으면 1, 거리두기 실패 0

 

알고가는 ppoint 

01. 주어진 규칙을 내 방식대로 새롭게 규정하는 것이 참 좋다. 

=> 코드가 명확하고 간결해짐.