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

이 문제는 주어진 격자 형태의 대기 공간에서 사람들이 적절한 거리에 앉아 있는지 확인하는 알고리즘을 구현하는 것이다.

먼저 5 x 5 격자 형태의 대기 공간이 있는데 각 셀은 다음과 같이 3가지 유형 중 하나일 수 있다.

• 'P' : 사람이 앉아 있는 곳
• 'O': 빈 자리
• 'X' : 파티션으로 구분된 자리

규칙은 다음과 같다.

1. 두 사람 사이에는 최소한 하나의 빈 자리가 있어야 한다. 이 규칙은 수평, 수직, 대각선 방향으로 적용된다. 2. 파티션('X')으로만 분리되어 있는 경우, 두 사람 사이의 거리가 어떤 경우에도 상관 없다.

나는 해당 문제를 해결하기위해 다음과 같은 과정을 생각했다.

1.각 대기 공간에 대해 반복하면서 사람들의 위치를 확인한다.

2. 각 사람의 위치에서 bfs(너비 우선 탐색)를 사용하여 주변에 다른 사람이 있는지 확인한다.

3. 만약 거리두기를 위반하는 경우를 발견하면 즉시 false를 반환한다.

4. 모든 사람의 위치에 대해 거리두기를 확인한 후, 모든 위치에서 거리두기를 만족하면 true를 반환한다.

코드는 아래와 같이 작성했다.

 

import java.util.*

class Solution {
    
    // 상하좌우 이동을 위한 배열 정의
    val dx = intArrayOf(-1, 1, 0, 0)
    val dy = intArrayOf(0, 0, -1, 1)

      
  
    fun solution(places: Array<Array<String>>): List<Int> {
        var answer = mutableListOf<Int>()
    
        for(place in places){
            if(check(place.map { it.toList() })){
                answer.add(1)
            }else{
                answer.add(0)
            }
        }
        
        return answer
    }
      // 거리두기를 확인하는 함수
    fun check(place:List<List<Char>>):Boolean
    {
          // 모든 위치에 대해 반복적으로 거리두기 확인
        for(i in place.indices){
            for(j in place[i].indices){
                  // 해당 위치에 사람이 있는지 확인
                if(place[i][j] == 'P'){
                     // 사람이 있다면 BFS를 통해 거리두기 확인
                    if(!bfs(i,j,place)){
                        return false // 거리두기를 만족하지 않으면 false 반환
                    }
                }
            }
        }
        return true
    }  
    
    fun bfs(x:Int,y:Int,place:List<List<Char>>):Boolean{
          // 방문 여부를 저장하는 배열
        val visited = Array(5){BooleanArray(5)}
        val queue = ArrayDeque<Triple<Int,Int,Int>>()
         // 시작 위치와 거리 0을 큐에 추가하고 방문 표시
        queue.offer(Triple(x,y,0))
        visited[x][y] = true
        
          // 큐가 비어있을 때까지 반복
        while(queue.isNotEmpty()){
             // 큐에서 위치와 거리를 가져옴
            val (curX,curY,dist) = queue.poll()
            // 거리가 1에서 2 사이에 있고 해당 위치에 사람이 있다면 거리두기를 위반함
            if (dist in 1..2 && place[curX][curY] == 'P') {
           
                return false  // 거리두기 위반 시 false 반환
        
            }
        
            if (dist > 2) {
            
                break
        
            }
              // 상하좌우 방향에 대해 탐색
            for(i in 0 until 4){
                val nx = curX + dx[i]
                val ny = curY + dy[i]
                val nd = dist + 1
                   
                // board 안에 들어와 있고, 벽이 아니고, 방문한적이 없다면 진행한다.
                if (nx in 0 until 5 && ny in 0 until 5 && place[nx][ny] != 'X' && !visited[nx][ny]) {
                
                     // 다음 위치를 큐에 추가
                    queue.offer(Triple(nx, ny, nd))
                     // 방문 표시
                    visited[nx][ny] = true
            
                }
            }
        }
        // 모든 위치에서 거리두기를 만족하면 true 반환
        return true
    }
  

}