[백준 7576번] [Kotlin] 토마토

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

7576번: 토마토

 

난이도 : 골드5
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

설명

주변(상하좌우, 대각선 X) 토마토를 익힌다 하였으니, BFS인걸 알 수 있다.

처음엔 초기 토마토 위치로 각각 BFS를 한 사이클씩만 돌리려 하였으나....

그럴수가 있나..? 하는 생각에 접근법을 달리 하였습니다.

 

한 사이클이 돌 때마다, x, y값이 -1인 값을 큐에 넣어 확인하여 한 사이클이 돌 때마다 일자를 +1씩 해주었습니다.

자세한건 코드와 함께 설명하겠습니다.

 

 

소스코드

 

data class Node(val x: Int, val y: Int)

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

x, y 좌표를 담을 Node 데이터 클래스를 만들고,

이동을 도와줄 dx와 dy 배열을 만든다.

 

 

인풋값 저장

val br = BufferedReader(InputStreamReader(System.`in`))
val mn = br.readLine()!!.split(" ") // m, n 순으로 입력받음
val n = mn[1].toInt()
val m = mn[0].toInt()

var day = 0

val map = Array(n) { Array(m) { 0 } }

val startNodes: Queue<Node> = LinkedList()

repeat(n) { x ->
    val st = StringTokenizer(br.readLine(), " ")
    repeat(m) { y ->
        map[x][y] = st.nextToken().toInt()
        if (map[x][y] == 1) {
            startNodes.offer(Node(x, y))
        }
    }
}

본 코드에서는 bufferedReader를 사용하여 입력을 받았습니다.

startNodes라는 리스트를 만들어 초기 토마토가 있는 위치를 저장해줍니다.

 

 

BFS

val q: Queue<Node> = LinkedList()
startNodes.forEach { q.offer(it) }

q.offer(Node(-1, -1))

 

q에 초기 토마토 위치 값들을 넣어주고,

한 사이클이 돌 때마다 -1, -1 좌표를 넣어 사이클이 하나 돌았다는 것을 알려주기 위해 -1, -1 좌표를 큐에 넣었습니다.

 

 

while (q.isNotEmpty()) {
    val target = q.poll()

    if (target.x == -1 && target.y == -1) {
        day++
        if (q.isNotEmpty()) {
            q.offer(Node(-1, -1))
        }
    }

    for (i in 0 until 4) {
        val nx = target.x + dx[i]
        val ny = target.y + dy[i]

        if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] == 1 || map[nx][ny] == -1)
            continue

        map[nx][ny] = 1
        q.offer(Node(nx, ny))
    }
}

 

그 이후는 다른 BFS 문제와 비슷하나,

 

if문을 사용해 큐에서 꺼낸 좌표값이 -1, -1 일 경우 사이클이 하나 돌았다는 것을 의미하므로

day를 +1 만큼 증가시키고,

 

현재 큐에는 한 사이클의 값이 온전히 다 들어있을 테니 -1, -1 좌표를 큐에 넣습니다.

 

단, 큐가 비어있을 경우 무한루프에 빠지는 것을 방지하기 위해 큐에 삽입하지 않습니다.

 

 

출력

map.forEach { it ->
    it.forEach { it2 ->
        if (it2 == 0) {
            println(-1)
            return
        }
    }
}

println(day - 1)

각 맵의 값을 하나씩 보면서, 0이 존재할 경우 -1을 출력하고,

그렇지 않을 경우 day에서 -1을 뺀 값을 출력합니다.

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import java.util.Queue
import java.util.StringTokenizer

data class Node(val x: Int, val y: Int)

var n = 0
var m = 0

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val mn = br.readLine()!!.split(" ") // m, n 순으로 입력받음
    val n = mn[1].toInt()
    val m = mn[0].toInt()

    var day = 0

    val map = Array(n) { Array(m) { 0 } }

    val startNodes: Queue<Node> = LinkedList()

    repeat(n) { x ->
        val st = StringTokenizer(br.readLine(), " ")
        repeat(m) { y ->
            map[x][y] = st.nextToken().toInt()
            if (map[x][y] == 1) {
                startNodes.offer(Node(x, y))
            }
        }
    }

    val q: Queue<Node> = LinkedList()
    startNodes.forEach { q.offer(it) }

    q.offer(Node(-1, -1))


    while (q.isNotEmpty()) {
        val target = q.poll()

        if (target.x == -1 && target.y == -1) {
            day++
            if (q.isNotEmpty()) {
                q.offer(Node(-1, -1))
            }
        }

        for (i in 0 until 4) {
            val nx = target.x + dx[i]
            val ny = target.y + dy[i]

            if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] == 1 || map[nx][ny] == -1)
                continue

            map[nx][ny] = 1
            q.offer(Node(nx, ny))
        }
    }

    map.forEach { it ->
        it.forEach { it2 ->
            if (it2 == 0) {
                println(-1)
                return
            }
        }
    }

    println(day - 1)
}

 

 

후기

처음에는 각 토마토의 위치에서 BFS를 한 사이클씩 돌리면 되겠군! 하면서 접근했으나

조금만 더 생각을 해보니까 ....그럴수가 있나....? 하면서 꽤 해맸던 문제였습니다. ㅠㅠ