[백준 15683번] [Kotlin] 감시

https://www.acmicpc.net/problem/15683

15683번: 감시

 

난이도 : 골드 4
태그 : 구현, 백트래킹, 브루트포스, 시뮬레이션

 

 

설명

기업 코테에서 정말 자주 나오는 문제 유형은 뭘까요?

사실 저도 기업코테를 많이 본 사람은 아니지만,

구현은 일단 안나온 적은 없었던 것 같고,

DFS/BFS/백트래킹도 정말 굉장히 자주 나왔던 것 같습니다.

구현 문제 중에서도 시뮬레이션 역시 단골 유형 중 하나인 것 같습니다.

분리집합/다익스트라 등도 좀 있던 것 같고요.

 

그런 의미에서 이번 문제는

백트래킹/브루트포스 + 구현 + 시뮬레이션이 섞인... 혼종이지만 코테 준비에는 꽤 좋을 것 같은 문제네요.

 

 

 

소스코드

import java.util.*
import kotlin.math.min

data class CCTV(val type: Int, val x: Int, val y: Int)

lateinit var originMap: Array<Array<Int>>
val cctv = ArrayList<CCTV>()
var n = 0
var m = 0
var min = Int.MAX_VALUE

fun main() = with(System.`in`.bufferedReader()) {
    val nm = readLine().split(" ").map { it.toInt() }
    n = nm[0]
    m = nm[1]

    originMap = Array(n) { x ->
        val st = StringTokenizer(readLine())
        Array(m) { y ->
            val value = st.nextToken().toInt()
            if (value in 1..5) cctv.add(CCTV(value, x, y))
            value
        }
    }

    backTracking(0, originMap)
    print(min)
}


fun backTracking(depth: Int, currentMap: Array<Array<Int>>) {
    if (depth == cctv.size) {
        val sum = currentMap.sumOf { it.count { it2 -> it2 == 0 } }
        min = min(min, sum)
        return
    }

    val cctvType = cctv[depth].type
    val maxDegree = when (cctvType) {
        1, 3, 4 -> 4
        2 -> 2
        5 -> 1
        else -> -1
    }

    for (degree in 0 until maxDegree) {
        val copiedMap = Array(n) { x -> Array(m) { y -> currentMap[x][y] } }

        when (cctvType) {
            1 -> cctvType1(cctv[depth], copiedMap, degree)
            2 -> cctvType2(cctv[depth], copiedMap, degree)
            3 -> cctvType3(cctv[depth], copiedMap, degree)
            4 -> cctvType4(cctv[depth], copiedMap, degree)
            5 -> cctvType5(cctv[depth], copiedMap)
        }
        backTracking(depth + 1, copiedMap)
    }
}

fun cctvType1(point: CCTV, map: Array<Array<Int>>, degree: Int) {
    when (degree) {
        // 오른쪽
        0 -> watchRight(point, map)
        // 아래
        1 -> watchDown(point, map)
        // 왼쪽
        2 -> watchLeft(point, map)
        // 위
        3 -> watchUp(point, map)
    }
}


fun cctvType2(point: CCTV, map: Array<Array<Int>>, degree: Int) {
    when (degree) {
        // 가로
        0 -> {
            watchRight(point, map)
            watchLeft(point, map)
        }

        // 세로
        1 -> {
            watchUp(point, map)
            watchDown(point, map)
        }
    }
}

fun cctvType3(point: CCTV, map: Array<Array<Int>>, degree: Int) {
    when (degree) {
        // 위, 오른쪽
        0 -> {
            watchRight(point, map)
            watchUp(point, map)
        }

        // 오른쪽, 아래
        1 -> {
            watchRight(point, map)
            watchDown(point, map)
        }

        // 아래, 왼쪽
        2 -> {
            watchDown(point, map)
            watchLeft(point, map)
        }

        // 왼쪽, 위
        3 -> {
            watchLeft(point, map)
            watchUp(point, map)
        }
    }
}

fun cctvType4(point: CCTV, map: Array<Array<Int>>, degree: Int) {
    when (degree) {
        // 오른쪽, 위, 아래
        0 -> {
            watchRight(point, map)
            watchUp(point, map)
            watchDown(point, map)
        }

        // 왼쪽, 오른쪽, 아래
        1 -> {
            watchLeft(point, map)
            watchRight(point, map)
            watchDown(point, map)
        }

        // 왼쪽, 위, 아래
        2 -> {
            watchLeft(point, map)
            watchUp(point, map)
            watchDown(point, map)
        }

        // 위, 왼쪽, 오른쪽
        3 -> {
            watchUp(point, map)
            watchLeft(point, map)
            watchRight(point, map)
        }
    }
}

fun cctvType5(point: CCTV, map: Array<Array<Int>>) {
    watchRight(point, map)
    watchLeft(point, map)
    watchUp(point, map)
    watchDown(point, map)
}

fun watchRight(p: CCTV, map: Array<Array<Int>>) {
    for (y in p.y until m) {
        if (map[p.x][y] == 6) break
        map[p.x][y] = -1
    }
}

fun watchLeft(p: CCTV, map: Array<Array<Int>>) {
    for (y in p.y downTo 0) {
        if (map[p.x][y] == 6) break
        map[p.x][y] = -1
    }
}

fun watchUp(p: CCTV, map: Array<Array<Int>>) {
    for (x in p.x downTo 0) {
        if (map[x][p.y] == 6) break
        map[x][p.y] = -1
    }
}

fun watchDown(p: CCTV, map: Array<Array<Int>>) {
    for (x in p.x until n) {
        if (map[x][p.y] == 6) break
        map[x][p.y] = -1
    }
}

 

 

CCTV class는 CCTV의 타입, x, y 좌표를 담고 있는 클래스입니다.

watchUp, down, left, right는 각각 상 하 좌 우를 감시하는 메소드인데요.

벽 (6)을 만날 때 까지 탐색합니다.

cctv는 타입 1~5에 따라, 그리고 방향에 따라 watch 메소드들을 조합하여 감시합니다.

 

그리고, 모든 cctv의 각도에 대해 백트래킹을 적용하여 답을 탐색합니다.

이 과정에서, 매번 새로운 map을 복사하여 건네줍니다.

 

 

 

후기

꽤... 오래 걸렸던 문제입니다.

구현 + 시뮬레이션 유형 특성 상 '아 이게 뭐지... 도저히 못풀겠다...' 보다는

'맞는데 왜 틀림?'을 외치며 예외를 잡아내는데 굉장히 많은 시간을 들였던 것 같습니다.

결국 정답을 받았지만 제출한 코드가 길고 중복되는 내용도 많아 맘에 들지 않아서,

watchUp/down/left/right 등 메소드로 나누고 이를 조합하는 방식으로 리팩토링 했는데, 조금 깔끔해진 것 같네요.