[백준] 7576번: 토마토 - kotlin

13522 단어 queueBFSBFS

문제

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

풀이

  • 자바의 Queue 자료구조를 사용
  • 1로 할당된 값을 트리의 루트로 가정
  • 0으로 할당된 값은 간선이 연결된 노드라고 가정
  • -1로 할당된 값은 간선이 연결되지 않은 노드라고 가정
  • BFS로 순회하며 트리의 높이를 계산
import java.util.*
import kotlin.math.max

fun getResult(tomatoes: MutableList<MutableList<Int>>, m: Int, n: Int): Int {
    var result = 0
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (tomatoes[i][j] == 0) return -1
            result = max(result, tomatoes[i][j])
        }
    }
    return result - 1
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (m, n) = br.readLine().split(" ").map { it.toInt() }
    val tomatoes = mutableListOf<MutableList<Int>>()
    repeat(n) {
        tomatoes.add(br.readLine().split(" ").map { it.toInt() }.toMutableList())
    }
    val dx = listOf(1, -1, 0, 0)
    val dy = listOf(0, 0, 1, -1)
    val queue: Queue<Pair<Int, Int>> = LinkedList()
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (tomatoes[i][j] == 1) {
                queue.add(Pair(i, j))
            }
        }
    }
    while (queue.isNotEmpty()) {
        val (y, x) = queue.poll()
        for (i in 0..3) {
            val nx = x + dx[i]
            val ny = y + dy[i]
            if (nx in 0 until m && ny in 0 until n && tomatoes[ny][nx] == 0) {
                queue.add(Pair(ny, nx))
                tomatoes[ny][nx] = tomatoes[y][x] + 1
            }
        }
    }
    bw.write("${getResult(tomatoes, m, n)}")
    br.close()
    bw.close()
}

더 좋은 방법 있으면 댓글 달아주세요!!!

좋은 웹페이지 즐겨찾기