[코틀린] 프로그래머스 - 거리두기 확인하기

---

전형적인 BFS 문제이다. 

최대한 함수로 역할을 나누어 분리해 풀이해보려고 노력했다.

 

solution -> check -> bfs 함수 순으로 내려가 보도록 하자.

 

 

📌  soloution 함수

fun solution(places: Array<Array<String>>): IntArray {
    var answer = mutableListOf<Int>()
    for (i in (0..4)) {
        if (check(places[i])) answer.add(1)
        else answer.add(0)
    }
    return answer.toIntArray()
}

문제에서 palaces가 2차원 String 배열로 주어지므로 한 줄씩 내려가면서 check 함수 안에 Array<String>을 넣어 만약 확인이 된다면 즉 거리두기를 위반하는 사람이 없다면 answer 리스트에 1을 넣어주고 위반한 사람이 존재하면 0을 넣어주자. 

 

이제 check 함수를 만들어보자.

 

 

📌  check 함수

fun check(place: Array<String>): Boolean {
    for (r in (0..4)) {
        for (c in (0..4)) {
            if (place[r][c] == 'P') {
                if (!bfs(place, r, c)) return false // 한명이라도 거리두기를 지키지 않았다면
            }
        }
    }
    return true // 모두 거리두기를 지켰다면
}

 check 함수에서는 인자로 한 줄의 String 즉 Array<String>이 넘어오게 된다. 이 한 줄이 하나의 대기실을 의미한다.

예를 들어 첫째줄 ["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"] 은

위 그림을 나타내는 대기실이 된다.

대기실의 크기는 5 X 5로 고정되어 있으므로 무난하게 2중 for문을 쓰도록 하자 

2중 for문을 돌면서 P를 만날 때, 즉 사람을 만날 때마다 bfs 함수를 수행해 한 명이라도 거리두기를 지키지 않았다면 false를 반환하고 모두 거리두기를 지켰다면 true를 반환하도록 한다.

 

이제 마지막 차례인 bfs 함수를 정의하도록 하자.

 

 

📌  bfs 함수

data class Point(val row: Int, val col: Int, val distance: Int)

val distanceArray = arrayOf(
    arrayOf(-1, 0),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(0, 1)
) // 상하좌우

fun bfs(place: Array<String>, row: Int, col: Int): Boolean {
    val visited = Array(5) { BooleanArray(5) } // Boolean 타입의 5 X 5 방문 행렬
    val queue = mutableListOf<Point>() // BFS 를 위한 큐
    visited[row][col] = true // 방문한 위치를 true 로 변경해준다.
    queue.add(Point(row, col, 0))

    while (queue.isNotEmpty()) {
        val curr = queue.removeFirst() // 큐의 poll()와 같은 기능
        if (curr.distance > 2) continue // 거리가 2를 넘어간다면 거리두기를 지킨것
        // 거리두기를 지키지 않은 사람을 발견했으므로 바로 false를 반환
        if (curr.distance != 0 && place[curr.row][curr.col] == 'P') return false 
        for (i in (0..3)) {
            val newRow = curr.row + distanceArray[i][0]
            val newCol = curr.col + distanceArray[i][1]
            if (newRow < 0 || newRow > 4 || newCol < 0 || newCol > 4) continue // 5 X 5 행렬을 넘어가지 않도록 처리
            if (visited[newRow][newCol]) continue // 이미 방문한 곳은 넘어가도록 처리
            if (place[newRow][newCol] == 'X') continue // 파티션이 있는 곳은 넘어가도록 처리
            visited[newRow][newCol] = true
            queue.add(Point(newRow, newCol, curr.distance + 1))
        }
    }
    return true
}

우선 row, col 위치와 distance를 가지고 있는 Point라는 data class를 만들어준다. 이렇게 만든 Point를 큐에 넣어 BFS를 해줄 것이다.

또한 탐색을 할 때 상하좌우를 움직여야 하므로 Array<Array<Int>> 타입의 distanceArray도 만들어준다. 마지막으로 bfs 함수 안에 방문 여부를 Boolean 타입으로 처리하는 visited를 만들어주고 BFS를 해줄 큐를 만들어준다.

 

이제 첫 위치를 방문처리를 해주고 큐에다가 초기값을 넣어주면서 BFS를 수행한다. 큐가 모두 비워질 때까지 큐의 첫 값을 하나씩 빼 주면 된다.(코틀린에서 큐는 LinkedList로 많이 수행하지만 이 문제에서는 그냥 MutableList를 썼다. 코딩테스트를 풀 때 나는 시간 복잡도에 큰 차이가 없으면 따로 라이브러리를 import 해주지 않기 위해 MutableList를 쓴다.)

만약 큐를 사용해야 하는데 그 범위가 크다면 MutableList가 아니라 LinkedList를 쓰는 것이 시간복잡도면에서 이점이 크다. MutableList를 큐로 사용한다면 첫 번째 원소를 제거하는 방식에서 문제가 발생한다. MutableList는 첫 번째 원소를 제거하면, 빈 자리를 채우기 위해 두 번째부터 마지막 원소를 전부 앞으로 한 칸씩 복사한다. 즉, MutableList는 제일 앞의 원소를 뺄 때마다 O(n)의 시간 복잡도가 발생한다. LinkedList는 반면에 첫 원소를 빼려면 그냥 header의 포인터를 두 번째 원소로 연결만 시키면 되는 구조이기 때문에 LinkedList는 O(1) 시간 복잡도만에 첫 원소를 제거하는 게 가능하다.

 

만약 거리두기를 지키지 않은 사람이 한 명이라도 발견된다면 그대로 false를 반환하면서 함수를 종료하고 한 명도 발견하지 않았다면 true를 반환해준다.