[백준][코틀린] 2842 집배원 한상덕

문제 내용

문제

상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.

매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.

상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌다. 상덕이가 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자. 이때, 가장 작은 피로도로 모든 집에 배달을 하려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)

다음 N개 줄에는 마을을 나타내는 행렬이 주어진다. 'P'는 한 번만 주어지며, 'K'는 적어도 한 번 주어진다.

다음 N개 줄에는 행렬로 나뉘어진 지역의 고도가 행렬 형태로 주어진다. 고도는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 가장 작은 피로도를 출력한다.

예제 입력	예제 출력
2 P. .K 2 1 3 2	0
3 P.. .KK … 3 2 4 7 4 2 2 3 1	2
3 K.P … K.K 3 3 4 9 5 9 8 3 7	5

문제 풀이

이번주 스터디로 이분탐색 문제를 풀기로해서 보던중 이문제를 골랐다. 문제를 읽고 나서 이문제에 어떻게 이분탐색을 적용하는지가 관권이였다. 한참을 최고 높이 - 최저 높이를 한 값으로 탐색을 생각하던중 불현듯 생각이 떠오른 것은 높이들에서 중복을 제거하고 이들을 정렬한 후 탐색하면서 범위를 찾아가면 되지 않을까?였다.

우선 값을 입력 받는다. 이때, 우체국의 좌표를 저장해두고(char == 'P'), 집의 갯수를 세어둔다 (char == 'K'). 또한, 높이 값은 추후 bfs에서 사용해야되므로 배열에도 저장해두고, set에도 저장해서 탐색 범위를 정해준다.

탐색범위는 정렬해준다. (heightSet.toSortedSet())

최저 높이를 heightSet의 원소를 순회하며 설정해주고 최고 높이를 이분 탐색을 통해 찾아준다. 이때, mid의 값이 최고 높이, i의 값이 최저 높이로 하여 BFS를 진행한다. deliveryPost 함수는 내부 주석을 참고해주세요! 

이때, BFS를 끝냈을 때 탐색해야할 집의 갯수가 0이라면 모두 다녀온 것이므로 true를 그렇지 않다면 false를 반환한다.

배달이 가능하다면 high의 값을 mid - 1을 해주고 결과 값을 갱신해준다.

배달이 가능하지 않다면 low의 값을 mid + 1 해준다.

모든 작업이 끝났을 때의 result 결과값을 출력해준다.!!

</>̆̈ 코드

import java.util.*

private val br = System.`in`.bufferedReader()
private val n = br.readLine().toInt()
private val board = Array(n) { CharArray(n) }; private val height = Array(n) { IntArray(n) }
private var heightSet = mutableSetOf<Int>()
private var result = Int.MAX_VALUE

private lateinit var postOffice: Pair<Int, Int>
private var houseCnt = 0

private val stepX = listOf(-1,  0,  1, -1, 0, 1, -1, 1)
private val stepY = listOf(-1, -1, -1,  1, 1, 1,  0, 0)

fun main() {
    for (row in 0 until n) {
        with(StringTokenizer(br.readLine())) {
            for ((col, char) in nextToken().withIndex()) {
                board[row][col] = char
                if (char == 'P') postOffice = Pair(row, col)
                if (char == 'K') houseCnt ++
            }
        }
    }
    for (row in 0 until n) {
        with(StringTokenizer(br.readLine())) {
            for (col in 0 until n) {
                height[row][col] = nextToken().toInt()
                heightSet.add(height[row][col])
            }
        }
    }
    heightSet = heightSet.toSortedSet()

    for (i in heightSet.indices) {
        var low = i; var high = heightSet.size - 1
        while (low <= high) {
            val mid = (low + high) / 2
            if (deliveryPost(heightSet.elementAt(i), heightSet.elementAt(mid))) {
                high = mid - 1; result = minOf(result, heightSet.elementAt(mid) - heightSet.elementAt(i))
            }
            else low = mid + 1
        }
    }

    print(result)
}

private fun deliveryPost(minimum: Int, maximum: Int): Boolean {
    // 우체국의 높이가 범위를 벗어날 경우 불가능한 경우
    if (height[postOffice.first][postOffice.second] !in minimum .. maximum) return false
    val visited = Array(n) {BooleanArray(n)}
    var visitHouse = houseCnt
    val queue = LinkedList<Pair<Int, Int>>()
    queue.add(postOffice); visited[postOffice.first][postOffice.second] = true

    while (queue.isNotEmpty()) {
        val (x, y) = queue.poll()
        for (i in 0 until 8) {
            val nx = x + stepX[i]; val ny = y + stepY[i]
            // 보드의 범위를 벗어날 때
            if (nx !in 0 until n || ny !in 0 until n) continue
            // 방문한적이 있을 때
            if (visited[nx][ny]) continue
            // 해당 좌표의 높이가 범위를 벗어날 때
            if (height[nx][ny] !in minimum .. maximum) continue
            if (board[nx][ny] == 'K') visitHouse -= 1
            visited[nx][ny] = true
            queue.add(Pair(nx, ny))
        }
    }

    return visitHouse == 0
}

링크

2842번: 집배원 한상덕