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

거리두기 확인하기

링크: 거리두기 확인하기

코딩테스트 연습 - 거리두기 확인하기

 

하나의 반에 대해서 다음을 수행한다.

1. 전체 순회를 돌며 각 사람에 대해서 bfs를 수행한다.
2. bfs를 수행하며, 빈 테이블일 경우 지나온 거리를 카운트 해서 저장한다.
3. bfs를 수행하다 사람을 만나게 될 경우 이전 빈테이블, 사람의 거리가 2 이하일 경우
   • 그 반은 적합하지 않다고 마킹한다.

위를 모든 반에 대해서 수행을 하고 마킹된 값을 읽어 answer 값에 담아 리턴한다.

 

• 정답 코드

import java.util.*

class Solution {
    val arrSize = 5
    val classDistance = Array(arrSize) { Array(arrSize) { Array(arrSize){0} } }
    val visited = Array(arrSize) { Array(arrSize) { Array(arrSize){false} } }
    val isOk = Array(arrSize) { true }

    val dx = arrayOf(1, -1, 0, 0)
    val dy = arrayOf(0, 0, 1, -1)

    var size = Pair(5, 5)

    fun validCheck(x: Int, y: Int): Boolean =
        (x < 0 || y < 0 || x >= size.first || y >= size.second)

    fun bfs(classNo:Int, map: Array<String>, start: Pair<Int, Int>): Boolean {
        var flag = false
        val queue: Queue<Pair<Int, Int>> = LinkedList()
        queue.add(start)
        visited[classNo][start.first][start.second] = true

        while (queue.isNotEmpty()) {
            val cur = queue.remove()
            for (i in 0 until 4) {
                val x = cur.first + dx[i]
                val y = cur.second + dy[i]

                if (validCheck(x, y) || visited[classNo][x][y]) continue
                visited[classNo][x][y] = true
                when (map[x][y]) {
                    'O' -> {
                        classDistance[classNo][x][y] = classDistance[classNo][cur.first][cur.second] + 1
                        queue.add(Pair(x, y))
                    }
                    'P' -> {
                        if(classDistance[classNo][cur.first][cur.second] + 1 <= 2){
                            isOk[classNo] = false
                            return true
                        }
                        queue.add(Pair(x, y))
                    }
                }
            }
        }
        return flag
    }

    fun solution(places: Array<Array<String>>): IntArray {
        val answer = mutableListOf<Int>()

        places.forEachIndexed { classNo, strings -> (0 until 5).forEach{ i -> repeat(5){k ->
            if(!visited[classNo][i][k] && places[classNo][i][k] == 'P' && bfs(classNo, places[classNo], Pair(i, k))) return@repeat
        } } }
        isOk.forEach { answer.add(if(it) 1 else 0) }

        return answer.toIntArray()
    }

}