[백준] 7576 (토마토)

#1 알고리즘

순회 문제다. bfs 문제일 것이다. '인접한 토마토'들을 모두 순회하고나서 '인접한 토마토에 인접한 토마토들'로 나아가는 형태여야 할 테니.
 

#2 여담

이게 한국정보올림피아드 고등부 문제였다니... 정말 대단한 사람들이다. 나는 수학적 계산 능력이 뛰어난 편은 아니며, 그 능력은 내 가치가 직접적으로 지향하는 바도 아니다. 하지만 이 문제가 골드5 난이도인 것을 명심해야 한다. 즉 이 정도는 난이도는 일상적으로 풀어낼 수 있어야 한다는 말이다. 열심히, 꾸준히 하자.
 

#3 코드 - 코틀린

lateinit var tomatoes: Array<Array<Int>>
var M = -2
var N = -2

fun main() {
    val mAndN = readln().split(" ")
    M = mAndN[0].toInt()
    N = mAndN[1].toInt()
    tomatoes = Array(N) { Array(M) { -2 } }

    var coordinateSet = HashSet<Pair<Int, Int>>()
    for (n: Int in 0..<N) {
        val rowOfN = readln().split(" ")
        for (m: Int in 0..<M) {
            val tomatoInfo = rowOfN[m].toInt()

            tomatoes[n][m] = tomatoInfo
            if (tomatoInfo == 1) {
                coordinateSet.add(Pair(n, m))
            }
        }
    }

    var day = -1
    while (coordinateSet.isNotEmpty()) {
        ripeTomato(coordinateSet)
        coordinateSet = getNextSet(coordinateSet)
        day++
    }

    if (findUnripe()) {
        println(-1)
    } else {
        println(day)
    }
}

fun findUnripe(): Boolean {
    for (row in tomatoes) {
        for (element in row) {
            if (element == 0) {
                return true
            }

        }
    }
    return false
}

fun getNextSet(coordinateSet: HashSet<Pair<Int, Int>>): HashSet<Pair<Int, Int>> {
    val nextSet = HashSet<Pair<Int, Int>>()

    for (coordinate in coordinateSet) {
        val candidates = listOf(
            Pair(coordinate.first + 1, coordinate.second),
            Pair(coordinate.first - 1, coordinate.second),
            Pair(coordinate.first, coordinate.second + 1),
            Pair(coordinate.first, coordinate.second - 1)
        )
        for (candidate in candidates) {
            val n = candidate.first
            val m = candidate.second

            if ((n in 0..<N) && (m in 0..<M) && (tomatoes[n][m] == 0)) {
                nextSet.add(candidate)
            }
        }

    }

    return nextSet
}

fun ripeTomato(coordinateSet: HashSet<Pair<Int, Int>>) {
    for (coordinate in coordinateSet) {
        tomatoes[coordinate.first][coordinate.second] = 1
    }
}

bfs지만 Queue가 필요 없는 문제다. 게다가, 중복된 좌표가 Queue에 들어갈 필요는 없다. 즉 (Queue 특유의) 순서도 필요없고 중복도 허용하지 않는다? Set이 딱이다.