[카카오] JS 거리두기 확인하기

전체 코드

function solution(places) {
    let answer = []
    for(const place of places){
      
        let isKeepDistance = true // 대기실의 거리두기 지킴 여부
        
        for(let i=0; i<5; i++){
            for(let j=0; j<5; j++){
              
              // 응시자를 만나면 해당 응시자의 좌표에서 bfs()로 그래프를 탐색한다
                if(place[i][j] === "P"){
                  
              // 만약 bfs()가 false이면 === 해당 응시자의 거리두기가 지켜지지 않으면 해당 대기실의 거리두기 지킴 여부를 false로 바꾼다
                    if(!bfs(i,j,place)){
                        isKeepDistance = false
                        break
                    }
                }
            }
        }
      // 대기실의 거리지킴 여부에 따라 answer결정한다
        if(isKeepDistance){
            answer.push(1)
        } else{
            answer.push(0)
        }
    }
    
    function bfs(i,j,place){
        const dirs = [[-1,0],[1,0],[0,1],[0,-1]]
        let visited = [[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
        let queue = [[i,j,0]]
        visited[i][j] = 1
        while(queue.length){
            const [y,x,distance] = queue.shift()
            if(distance === 2){
                continue
            }
            for(const dir of dirs){
                const nextY = y + dir[0]
                const nextX = x + dir[1]
                
                if(nextX < 0 || nextY < 0 || nextX >=5 || nextY >=5 ){
                    continue
                }
                if(place[nextY][nextX] === "X"){
                    continue
                }
                if(visited[nextY][nextX] === 1){
                    continue
                }
                if(place[nextY][nextX] === "P"){
                    return false
                }
                visited[nextY][nextX] = 1
                queue.push([nextY,nextX,distance+1])
            }
        }
        return true
    }
    return answer
}

복기

1. 백준 미로탐색을 풀고나서 이 문제를 풀었더니 비슷해서 그런가 수월했다.
2. 문제의 차이점은 좌표와 함께 거리를 저장하고, 거리가 2인 경우는 queue에 넣지 않는것 뿐이다
3. 하나의 place에는 여러개의 시작점 (P)가 있어서 for문을 다 돌때까지 기다리기 위해 플래그인 ok를 두었다. 플래그를 사용하지 않는 더 나은 방법이 있을까?
4. 문제에서 행의 길이와 열의 길이가 5로 고정되어 있어서 visited 배열의 초기값을 설정할 수 있었다.
5. queue에 넣지 않을(그래프 탐색을 하지않을) 예외 조건을 나누어 적었다.

// distance가 2인 경우에는 그래프 탐색을 하지 않는다, 애초에 queue에 넣지 않는 방법도 있을 것 같다
if(distance === 2){
  continue
}


// 좌표가 그래프를 벗어나는 경우
if(nextX < 0 || nextY < 0 || nextX >=5 || nextY >=5 ){
  	continue
}

// 막힌 경우
if(place[nextY][nextX] === "X"){
  	continue
}

// 이미 방문했던 좌표인 경우
if(visited[nextY][nextX] === 1){
  	continue
}

// P를 만나면 거리두기를 지키지 않았기 때문에 바로 return한다
if(place[nextY][nextX] === "P"){
  	return false
}

6. queue를 다 돌면 거리두기가 지켜졌다는 이야기라서 return true를 해준다

7. 자바스크립트와 파이썬에서truthy falsy 값이 다르다

while(queue.length)  // 길이를 해주어야한다. JS에서 []는 Truthy하다

while queue // queue만 적어줘도 된다. python에서 []는 Falsy하다