[Kotlin/프로그래머스] 거리두기 확인하기 (2021 카카오 채용연계형 인턴십)

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

 

[문제 소개]

1. 5 * 5 이차원 배열의 대기실이 주어졌을 때

2. 맨해튼 거리로 2 이하가 되게 사람이 존재해서는 안된다는 거리제한 조건

3. 단, 벽이 존재하여 상하좌우 4방향 기준으로 가는 길이 막혔다면 2 이하여도 거리두기를 준수함

사람 P, 빈테이블 O, 벽 X

 

[문제 이해]

P 를 정점으로생각하고 O 를 다른 P 로 이어주는 간선으로 생각한다면 2 차원 배열 그래프를 그릴 수 있다.

bfs 최단거리로 P 면서 거리가 2 이하라면 거리두기를 지키지 않은 것이다.

모든 P 가 검사 대상이다.

방마다 검사해준다.

 

[코드]  

import java.util.*


class Solution {
    val size = 5
    val dx = arrayOf(1, -1, 0, 0)
    val dy = arrayOf(0, 0, 1, -1)
    
    
    fun solution(places: Array<Array<String>>): IntArray {
        var ans = mutableListOf<Int>()

        places.forEach { place ->
            val result = obeyDistance(place)
            ans.add(result)
        }
        var answer: IntArray = ans.toIntArray()

        return answer
    }
    fun obeyDistance(place: Array<String>): Int {
        for (i in place.indices) {
            for (j in 0 until place[i].length) {
                val cur = place[i][j]
                if (cur == 'P') {
                    if (!bfs(place, i, j)) {
                        return 0
                    }
                }
            }
        }
        return 1
    }

    fun bfs(place: Array<String>, startX: Int, startY: Int): Boolean {
        val q: Queue<Int> = LinkedList<Int>()
        q.add(startX)
        q.add(startY)
        val board: Array<Array<Int>> = Array(5) { Array(5) { 0 } }
        
        while(!q.isEmpty()) {
            val curX = q.poll()
            val curY = q.poll()
            var distance = board[curX][curY] + 1
           
          
            if (distance > 2) {
                return true
            }
            
            for (i in 0..3) {
                val nx = curX + dx[i]
                val ny = curY + dy[i]
                
                if (!isIn(nx, ny)) { continue }
                
                if (nx == startX && ny == startY) { continue } 
                
                if (place[nx][ny] != 'X' && board[nx][ny] == 0) {
                    q.add(nx) 
                    q.add(ny)
                    board[nx][ny] = distance
                }
                
                if (place[nx][ny] == 'P' && board[nx][ny] <= 2) {
                    return false
                }
            }
        }
        return true
    }
    private fun isIn(x: Int, y: Int): Boolean = (x >= 0 && x < size && y >= 0 && y < size) 
}

 

 

 

[공부해서 추가할 내용]

- 더 코틀린스러운 코드로 리팩토링

- 굳이 bfs 를 써야할까? 다른 사람의 풀이를 살펴보고 내용을 추가하자