BOJ1036 성지키기

Overview

• Problem: https://www.acmicpc.net/problem/1236
• TimeComplexity: O(nm) / 행열 탐색을 위한 이중 포문이 최대 시간 / n,m이 최대값이 50이므로 충분히 시간내 풀 수 있다.
• Type: 행열
• Git: https://github.com/kylelab/algorithms/blob/main/src/boj/BOJ1036.kt

Solution

• 경비원이 없는 행과 열의 갯수를 구한 후 그 중 최대값을 출력한다.
• 모든 행에 한개씩 채우고, 나머지 열에 한개씩 채우는 것이 경비원의 최소값이므로, 행과 열중 큰 값이 정답이 된다. 

Solution1 

• 이중 포문으로 각 행에 경비원이 포함되었는지 확인하고 총 행 수에서 경비원수를 뺀다.

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n, m) = br.readLine().split(" ").map { it.toInt() }
    val array: Array<CharArray> = Array(n) {
        br.readLine().toCharArray()
    }
    br.close()

    val (nonIncludedRow, nonIncludedCol) = solution1(array, m, n)
    println(max(nonIncludedRow, nonIncludedCol))
}

private fun solution1(
    array: Array<CharArray>,
    m: Int,
    n: Int
): Pair<Int, Int> {
    var includedRow = 0
    for (row in array) {
        for (i in 0 until m) {
            if (row[i] == 'X') {
                includedRow++
                break
            }
        }
    }
    val nonIncludedRow = n - includedRow

    var includedCol = 0
    for (j in 0 until m) {
        for (i in 0 until n) {
            if (array[i][j] == 'X') {
                includedCol++
                break
            }
        }
    }
    val nonIncludedCol = m - includedCol
    return Pair(nonIncludedRow, nonIncludedCol)
}

 

Solution2

• 1처럼 행/열 각각 도는게 아니라 한번에 돌면서 경비원이 있는 행/열인지 체크해서 계산한다. 

private fun solution2(
    array: Array<CharArray>,
    m: Int,
    n: Int
): Pair<Int, Int> {
    val includedRow = BooleanArray(n)
    val includedCol = BooleanArray(m)

    for (i in 0 until n) {
        for (j in 0 until m) {
            if (array[i][j] == 'X') {
                includedRow[i] = true
                includedCol[j] = true
            }
        }
    }

    var nonIncludedRowCount = n
    for (i in 0 until n) {
        if (includedRow[i]) {
            nonIncludedRowCount--
        }
    }

    var nonIncludedColCount = m
    for (i in 0 until m) {
        if (includedCol[i]) {
            nonIncludedColCount--
        }
    }

    return Pair(nonIncludedRowCount, nonIncludedColCount)
}