[백준] 15683 감시

 

🔒 문제

 

🧠 아이디어

경우의수 - Backtracking 가능 여부

모든 CCTV가 동서남북 90도로만 회전 가능하다.

CCTV 종류별로 다른 감시 영역을 갖도록하는 회전 횟수는 다음과 같다.

1번 : 4회

2번: 2회

3번: 4회

4번: 4회

5번: 1회

최대 CCTV 개수가 8개로 제한되어 있으므로 가장 경우의수가 많은 4회 기준 

$$ 4^8\;=2^{16}\ $$

약 6만 4천회므로 Backtracking 으로 모든 경우의 수를 따져보면 되겠다.

전체 킹우의 수를 어떻게 표현해야할까

 

 

모든 배열에 대한 조합이 필요하다.

이게 좀 빡치는데..

각  CCTV 설치 지점으로부터의 방향 쌍에대한 모든 조합을 미리 keep 해둬서 구현했다.

2차원 배열에서 모든 배열의 쌍에 대한 조합을 구하는 코드가 GeeksForGeeks 에 소개되어있다.

 

⚠️ CCTV가 없는 엣지케이스

CCTV가 설치되지 않는 케이스도 구해야한다.

 

⚠️ 한 번 실수하면 개망한다.

이런 구현류의 문제는 디버깅하기가 정말 어렵다.

테스트 케이스를 스스로 만들기도 어렵다. 그냥 최고의 집중력으로 한땀한땀 온 정신을 쏟아서 구현해야한다...

 

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

// key: cctv 좌표, value: kind
data class CCTV(val X: Int, val Y: Int, val type: Int) {

}

// key: cctv type, value: rotate kind
private val cctvMap = mapOf<Int, Array<String>>(
    1 to arrayOf("up", "right", "down", "left"),
    2 to arrayOf("horizontal", "vertical"),
    3 to arrayOf("upRight", "rightDown", "downLeft", "leftUp"),
    4 to arrayOf("leftUpRight", "upRightDown", "rightDownLeft", "downLeftUp"),
    5 to arrayOf("cardinalDirection")
)

// # 대신 -1 로 대치하면됨.
private fun bfs(cctvPoint: CCTV, direction: String, map: Array<IntArray>) {
    // 아 여기서 타입을 어케나누지 cctvMap 사용해서 타입별로 CCTV 감시구역 마킹하면되는데
    // 총 14가지 cctv 감시 모두 때리면될듯
    val (startRowIdx, startColIdx) = cctvPoint

    var rightColIdx = startColIdx + 1
    var leftColIdx = startColIdx - 1
    var upRowIdx = startRowIdx - 1
    var downRowIdx = startRowIdx + 1

    when(direction) {
        // 1번
        "up"-> {
            while (upRowIdx >= 0 && map[upRowIdx][startColIdx] != 6) map[upRowIdx--][startColIdx] = -1
        }
        "right"-> {
            while (rightColIdx < map[0].size && map[startRowIdx][rightColIdx] != 6) map[startRowIdx][rightColIdx++] = -1
        }
        "down"-> {
            while (downRowIdx < map.size && map[downRowIdx][startColIdx] != 6) map[downRowIdx++][startColIdx] = -1
        }
        "left"-> {
            while (leftColIdx >= 0 && map[startRowIdx][leftColIdx] != 6) map[startRowIdx][leftColIdx--] = -1
        }

        // 2번
        "horizontal"-> {
            while (rightColIdx < map[startRowIdx].size && map[startRowIdx][rightColIdx] != 6) map[startRowIdx][rightColIdx++] = -1
            while (leftColIdx >= 0 && map[startRowIdx][leftColIdx] != 6) map[startRowIdx][leftColIdx--] = -1
        }
        "vertical"-> {
            while (upRowIdx >= 0 && map[upRowIdx][startColIdx] != 6) map[upRowIdx--][startColIdx] = -1
            while (downRowIdx < map.size && map[downRowIdx][startColIdx] != 6) map[downRowIdx++][startColIdx] = -1
        }

        // 3번
        "upRight"-> {
            while (upRowIdx >= 0 && map[upRowIdx][startColIdx] != 6) map[upRowIdx--][startColIdx] = -1
            while (rightColIdx < map[startRowIdx].size && map[startRowIdx][rightColIdx] != 6) map[startRowIdx][rightColIdx++] = -1
        }
        "rightDown"-> {
            while (rightColIdx < map[startRowIdx].size && map[startRowIdx][rightColIdx] != 6) map[startRowIdx][rightColIdx++] = -1
            while (downRowIdx < map.size && map[downRowIdx][startColIdx] != 6) map[downRowIdx++][startColIdx] = -1
        }
        "downLeft"-> {
            while (downRowIdx < map.size && map[downRowIdx][startColIdx] != 6) map[downRowIdx++][startColIdx] = -1
            while (leftColIdx >= 0 && map[startRowIdx][leftColIdx] != 6) map[startRowIdx][leftColIdx--] = -1
        }

        "leftUp"-> {
            while (leftColIdx >= 0 && map[startRowIdx][leftColIdx] != 6) map[startRowIdx][leftColIdx--] = -1
            while (upRowIdx >= 0 && map[upRowIdx][startColIdx] != 6) map[upRowIdx--][startColIdx] = -1
        }

        // 4번
        "leftUpRight"->{
            while (leftColIdx >= 0 && map[startRowIdx][leftColIdx] != 6) map[startRowIdx][leftColIdx--] = -1
            while (upRowIdx >= 0 && map[upRowIdx][startColIdx] != 6) map[upRowIdx--][startColIdx] = -1
            while (rightColIdx < map[startRowIdx].size && map[startRowIdx][rightColIdx] != 6) map[startRowIdx][rightColIdx++] = -1
        }
        "upRightDown"-> {
            while (upRowIdx >= 0 && map[upRowIdx][startColIdx] != 6) map[upRowIdx--][startColIdx] = -1
            while (rightColIdx < map[startRowIdx].size && map[startRowIdx][rightColIdx] != 6) map[startRowIdx][rightColIdx++] = -1
            while (downRowIdx < map.size && map[downRowIdx][startColIdx] != 6) map[downRowIdx++][startColIdx] = -1
        }
        "rightDownLeft"-> {
            while (rightColIdx < map[startRowIdx].size && map[startRowIdx][rightColIdx] != 6) map[startRowIdx][rightColIdx++] = -1
            while (downRowIdx < map.size && map[downRowIdx][startColIdx] != 6) map[downRowIdx++][startColIdx] = -1
            while (leftColIdx >= 0 && map[startRowIdx][leftColIdx] != 6) map[startRowIdx][leftColIdx--] = -1
        }
        "downLeftUp"-> {
            while (downRowIdx < map.size && map[downRowIdx][startColIdx] != 6) map[downRowIdx++][startColIdx] = -1
            while (leftColIdx >= 0 && map[startRowIdx][leftColIdx] != 6) map[startRowIdx][leftColIdx--] = -1
            while (upRowIdx >= 0 && map[upRowIdx][startColIdx] != 6) map[upRowIdx--][startColIdx] = -1
        }

        // 5번
        "cardinalDirection"-> {
            // 동서남북 다
            while (upRowIdx >= 0 && map[upRowIdx][startColIdx] != 6) map[upRowIdx--][startColIdx] = -1
            while (rightColIdx < map[startRowIdx].size && map[startRowIdx][rightColIdx] != 6) map[startRowIdx][rightColIdx++] = -1
            while (downRowIdx < map.size && map[downRowIdx][startColIdx] != 6) map[downRowIdx++][startColIdx] = -1
            while (leftColIdx >= 0 && map[startRowIdx][leftColIdx] != 6) map[startRowIdx][leftColIdx--] = -1

        }
    }
}

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))

    val (rowSize, colSize) = bufferedReader.readLine().split(" ").map(String::toInt)

    val map: Array<IntArray> = Array(rowSize){
        bufferedReader.readLine().split(" ").map(String::toInt).toIntArray()
    }

    val stringBuilder = StringBuilder()

    val cctvPoints = LinkedList<CCTV>()

    for (row in map.indices) {
        for (col in map[row].indices) {
            if (map[row][col] in 1..5) cctvPoints.add(CCTV(row, col, map[row][col]))
        }
    }

    // CCTV 가 없는 케이스
    if (cctvPoints.size == 0) {
        var zeroCnt = 0
        for (arr in map) {
            zeroCnt += arr.count { it == 0 }
        }
        print(zeroCnt)
        return
    }
    // 여기서 모든 rotate 방향에 대한 총 포인트 시작점들의 kind array 조합만 되면 모든게 해결됨.
    // (point index 에 해당하는 방향 모든 조합이 완성되기 때문에 한 싸이클 끝날 때마다 조지면됨.)

    // cctv 모든 타입에 대한 회전 정보 조합만 가지고 그애들에 대해 모두 DFS 때리면 됨.
    val types = cctvPoints.map { cctvMap[it.type]!! }

    // direction 의 모든 조합 set 개수
    val directions = LinkedList<LinkedList<String>>()
    // 모든 조합 구하기.
    val indices = IntArray(types.size)

    var directionIdx = 0
    while (true) {
        directions.add(LinkedList<String>())
        for (i in types.indices) {
            stringBuilder.append("${types[i][indices[i]]} ")
            directions[directionIdx].add(types[i][indices[i]])
        }
        directionIdx++

        stringBuilder.appendLine()

        var next = types.size - 1
        while (next >= 0 && indices[next] + 1 >= types[next].size) next--

        if (next < 0 ) break

        indices[next]++

        for (i in next + 1 until types.size) indices[i] = 0
    }

    var tempMap = map.map { it.clone() }.toTypedArray()

    var answer = colSize * rowSize
    var zeroCnt = 0
    for (directionArr in directions) {
        directionArr.forEachIndexed { idx, direction ->
            bfs(cctvPoints[idx], direction, tempMap)
        }

        // count 0 개수 in tempMap
        for (arr in tempMap) {
            zeroCnt += arr.count { it == 0 }
        }
        answer = min(answer, zeroCnt)
        zeroCnt = 0
        // reset tempMap by map
        tempMap = map.map { it.clone() }.toTypedArray()

    }

    print(answer)
}

 

⚒️ Refactoring

2차원 배열에 방향쌍을 담아 모든 순열을 구하는 Backtracking  방식보다 더 간단한 방법은 없을까?

 

방향이 4개로 고정되어 있으므로 (2, 5번 제외) 밑을 4로 두고 CCTV 개수만큼을 지수승하면 모든 순열을 구할 수 있다.

각 자리에 올 값이 모두 숫자이며 고정 범위일 때
N진법을 사용하면 Backtracking 보다 쉽게 모든 경우의 수를 표현할 수 있다.

 

 

 

모든 경우의 수 (CCTV 별 방향 매칭) 에 대해 감시 영역을 -1로 색칠하는 함수를 작성하고

사각지대의 최소 값을 구해보자

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

// 4진법에서 표현된 숫자가 의미하는 방향
enum class Direction {
    SOUTH, // 0
    EAST,  // 1
    NORTH, // 2
    WEST   // 3
}

private val dx = intArrayOf(1, 0, -1, 0)
private val dy = intArrayOf(0, 1, 0, -1)

data class CCTV(val X: Int, val Y: Int, val type: Int) {

}

private fun isOutOfBoundary(row: Int, col: Int, map: Array<IntArray>) : Boolean{
    return row < 0 || col < 0 || row >= map.size || col >= map[0].size
}

// 한 방향으로만 색칠
// 이미 특정 CCTV의 방향은 결정된 상태로 색칠만 조지게 하기.
private fun surveilFromCCTV(startRow: Int, startCol: Int, direction: Int, map: Array<IntArray>) {
    val realDirection = direction % 4
    var nextRow = startRow
    var nextCol = startCol
    while (true) {
        // 오로지 남동북서 중 1개만 가짐
        nextRow += dx[realDirection]
        nextCol += dy[realDirection]

        // 범위를 벗어났거나 벽을 만나면 색칠 종료
        if (isOutOfBoundary(nextRow, nextCol, map) || map[nextRow][nextCol] == 6) return
        // CCTV 거나 이미 감시가 되고 있는 지역이면 다음으로 통과 (사실 이 코드는 없어도 됨)
        if (map[nextRow][nextCol] != 0) continue
        map[nextRow][nextCol] = -1
    }

}

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))

    val (rowSize, colSize) = bufferedReader.readLine().split(" ").map(String::toInt)

    val originalMap: Array<IntArray> = Array(rowSize){
        bufferedReader.readLine().split(" ").map(String::toInt).toIntArray()
    }

    val cctvPoints = LinkedList<CCTV>()

    var answer = 0

    // (1) 1st cctv point 넣고
    for (row in originalMap.indices) {
        for (col in originalMap[row].indices) {
            if (originalMap[row][col] in 1 .. 5) cctvPoints.add(CCTV(row, col, originalMap[row][col]))
            // 태초의 상태에서 0의 개수는 미리 구해놔야함. (CCTV 가 1개 이상 설치된다는 보장이 없음.)
            else if (originalMap[row][col] == 0) answer++
        }
    }

    // (2) 모든 CCTV-방향 쌍의 순열 경우의 수 구하기
    // 총 경우의 수 == 자리 수 (4) ^ cctv 개수 == 2 ^ (2 * cctv 개수)
    val maxPosCnt = 1 shl (2 * cctvPoints.size)
    for (num in 0 until maxPosCnt) {
        // 매 case 마다 임시 지도를 초기화 해야함
        val tempMap = Array(originalMap.size){ idx-> originalMap[idx].copyOf()}

        var nextNum = num

        for (cctv in cctvPoints) {
            // 각 cctv 별 방향 결정 (첫번째 자리)
            val curDirection = nextNum % 4
            // 다음번 방향을 결정할 수 있게 이미 사용한 첫번째 자리 제거
            nextNum /= 4
            
            // 방향이 정해진 상태면 CCTV 종류에 따라서 각 방향에 색칠을 때려야함.
            // 모든 방향은 1개의 방향만 가짐. (타입별로 여기서 분기)
            val (row, col, type) = cctv

            when (type) {
            	// 남동북서 중 1방향
                1 -> surveilFromCCTV(row, col, curDirection, tempMap)
                2 -> {
                // 무조건 수평 || 수직 2방향
                    surveilFromCCTV(row, col, curDirection, tempMap)
                    surveilFromCCTV(row, col, curDirection + 2, tempMap)
                }
                3 -> {
                // 2방향 ㄱ자 모양
                    surveilFromCCTV(row, col, curDirection, tempMap)
                    surveilFromCCTV(row, col, curDirection + 1, tempMap)
                }
                4 -> {
                // 3방향 ㅗ 자 모양
                    surveilFromCCTV(row, col, curDirection, tempMap)
                    surveilFromCCTV(row, col, curDirection + 1, tempMap)
                    surveilFromCCTV(row, col, curDirection + 2, tempMap)
                }
                5 -> {
                // 4방향 모두
                    surveilFromCCTV(row, col, curDirection, tempMap)
                    surveilFromCCTV(row, col, curDirection + 1, tempMap)
                    surveilFromCCTV(row, col, curDirection + 2, tempMap)
                    surveilFromCCTV(row, col, curDirection + 3, tempMap)
                }
            }

        }
        // (3) (1, 2) 에서 구한 순열을 하나씩 돌리며 case 1개 별로 사각지대 구하기
        var zeroCnt = 0
        for (row in tempMap) {
            for (value in row) if (value == 0) zeroCnt++
        }

        // (4) (3) 에서 구한 사각지대 개수 중 최소 값을 정답으로 처리.
        answer = min(answer, zeroCnt)
    }

    print(answer)
}

 

 

🔑 Kotlin Code 

5번 cctv 는 방향이 어차피 0 하나로만 결정되도 동서남북을 모두 갈 것이고

2번 cctv는 (0,2), (1,3) 등 수직/수평이나 (2,4), (3,5) 나 같은 방향이므로 continue 로 조금이나마 최적화가 가능하다.

다음 코드는 2번에서 direction 이 2 이상이거나

5번에서 direction 이 0이 아닐 때 감시를 스킵하여 0의 최대 갯수(최적의 해) 가 아닌케이스로 조금이라도 연산량을 줄이는 코드다. 

(실제로 해당 케이스의 모든 CCTV 감시를 스킵하는게 아니라 2번, 5번 CCTV의 지정된 방향 이외에는 감시를 스킵하여 최적의 해가 절대 아니도록 하는 방식)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

// 남 동 북 서
private val dx = intArrayOf(-1, 0, 1, 0)
private val dy = intArrayOf(0, 1, 0, -1)

fun isOutOfBoundMap(rowIdx: Int, colIdx: Int, tempMap: Array<IntArray>) : Boolean {
    return rowIdx < 0 || colIdx < 0 || rowIdx >= tempMap.size || colIdx >= tempMap[0].size
}

// 감시 작업
// 정해진 cctv 좌표로부터 정해진 direction: 0 ~ 4 으로 줄곧 이동
fun surveilByCCTV(row: Int, col: Int, direction: Int, tempMap: Array<IntArray>) {
    val curDirection = direction % 4
    var nextRow = row + dx[curDirection]
    var nextCol = col + dy[curDirection]

    while (!isOutOfBoundMap(nextRow, nextCol, tempMap)) {
        // 벽 만나면 색칠 종료
        if (tempMap[nextRow][nextCol] == 6) return
        else if (tempMap[nextRow][nextCol] == 0) tempMap[nextRow][nextCol] = -1

        // 정해진 방향으로 한 칸씩 이동
        nextRow += dx[curDirection]
        nextCol += dy[curDirection]
    }
}

fun getCountOfBlindSpot(tempMap: Array<IntArray>): Int {
    var zeroCnt = 0
    for (row in tempMap.indices) {
        for (col in tempMap[row].indices) {
            if (tempMap[row][col] == 0) zeroCnt++
        }
    }

    return zeroCnt
}

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = bufferedReader.readLine().split(" ").map(String::toInt)

    val map = Array(N){idx->
        bufferedReader.readLine().split(" ").map(String::toInt).toIntArray()
    }

    val cctvPoints = LinkedList<IntArray>()

    var answer = 0
    // 1. 원본 배열 순회하며 cctv point keep.
    // 0 개수도 answer 후보로 keep (cctv 미설치 케이스가 존재함)
    for (row in map.indices) {
        for (col in map[row].indices) {
            if (map[row][col] in 1 .. 5) cctvPoints.add(intArrayOf(row, col))
            else if (map[row][col] == 0) answer++
        }
    }

    // cctv - 방향 쌍 총 순열 경우의 수 == 4^CCTV 수 == 2 ^ (2 * CCTV 수)
    val numOfCases = 1 shl (2 * cctvPoints.size)
    for (num in 0 until numOfCases) {
        val tempMap = Array(map.size){idx -> map[idx].copyOf()}
        var nextNum = num
        for (point in cctvPoints) {
            // num 은 cctv 수만큼 자리수를 가짐.
            // 따라서 cctv 수만큼 나눠져서 끝자리까지 다 검사해야함.
            // 각 케이스를 순회하며 임시 맵에 색칠
            val curDirection = nextNum % 4
            val (row, col) = point
            // 임시 지도에 색칠
            // 카메라 종류마다 색칠 방법이 다름.

            when (map[row][col]) {
                1 -> {
                    surveilByCCTV(row, col, curDirection, tempMap)
                }
                2 -> {
                    // 방향쌍이 (0-2) 수직, (1-3) 수평 만 의미있음.
                    // (2-4), (3-5) 는 어차피 중복이기 때문에 skip
                    if (curDirection >= 2) continue
                    surveilByCCTV(row, col, curDirection, tempMap)
                    surveilByCCTV(row, col, curDirection + 2, tempMap)
                }
                3 -> {
                    surveilByCCTV(row, col, curDirection, tempMap)
                    surveilByCCTV(row, col, curDirection + 1, tempMap)
                }
                4 -> {
                    surveilByCCTV(row, col, curDirection, tempMap)
                    surveilByCCTV(row, col, curDirection + 1, tempMap)
                    surveilByCCTV(row, col, curDirection + 2, tempMap)
                }
                5 -> {
                    // 어차피 모든 방향에 대해 (0,1,2,3) 다 갈 것이므로 그 이상의 숫자는 의미 없음.
                    if (curDirection != 0) continue
                    surveilByCCTV(row, col, 0, tempMap)
                    surveilByCCTV(row, col, 1, tempMap)
                    surveilByCCTV(row, col, 2, tempMap)
                    surveilByCCTV(row, col, 3, tempMap)
                }
            }

            nextNum /= 4
        }

        // 한 케이스에 대한 색칠이 종료됐으면 0의 개수를 카운팅
        val zeroCnt = getCountOfBlindSpot(tempMap)
        answer = min(answer, zeroCnt)
    }

    print(answer)
}

 

 

---

🔗 Reference

Combinations from n arrays picking one element from each array - GeeksforGeeks

Print all possible combinations of r elements in a given array of size n - GeeksforGeeks