<백준> 토마토(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/%ED%86%A0%EB%A7%88%ED%86%A0

[백준]

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

 

뒤의 BFS를 작성하는 것보다 입력받는게 힘들었다.

정말 2차원 배열 입력받을 때는 자바나 C가 조금 그리워진다.

프로그래머스 문제와 다르게 백준에서는 입력부터 시작이기 때문에 진짜 익숙치가 않다.

정말 다양하게 입력을 받았다.

with 사용해보고 repeat도 사용해봤다.

 

2차원 배열 원소 개수 구하는 것도 조금 복잡했다.

count 함수를 중첩시켜 했는데 이게 맞나...? 싶다.

 

이후 BFS를 진행할 때는 한 사이클이 돌았다는 것을 판별하기위해 더미 데이터를 집어넣었다.

그 더미데이터에 도착하면 count 값을 1증가시키고 다시 더미 데이터를 집어넣었다.

이러다가 더미데이터가 무한히 들어갔다 나갔다 하게 되는 코드를 보게 되었는데 이 부분은 현재 큐가 비어있다면 더미 데이터를 추가하지 않는 걸로 해서 마무리될 수 있게 했다.

 

다른 것보다 입력과 2차원 배열 접근이 힘들었던 문제였던 거 같다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.util.StringTokenizer

var m: Int = 0
var n: Int = 0
var farm = mutableListOf<MutableList<Int>>()
lateinit var visited: Array<Array<Boolean>>
val q = ArrayDeque<Pair<Int, Int>>()
val dy = listOf(0, 1, 0, -1)
val dx = listOf(1, 0, -1, 0)

fun main() = with(System.`in`.bufferedReader()) {
    // 행, 열 값 받기
    with(StringTokenizer(readln())) {
        m = nextToken().toInt()
        n = nextToken().toInt()
    }
    
    // 2차원 리스트 값 받기
    repeat(n) {
        farm.add(readln().split(" ").map { it.toInt() }.toMutableList())
    }

    // 방문 여부 확인용 배열 지연 초기화
    visited = Array(n) { Array(m) { false } }

    // 모든 토마토가 익어있는 상태인지 확인
    if (farm.count { it.count { num -> num == 1 } == m } == n) {
        println(0)
        return
    }

    // 익어있는 토마토 찾기
    farm.forEachIndexed { row, line ->
        line.forEachIndexed { col, num ->
            if (num == 1) {
                q.add(Pair(row, col))
                visited[row][col] = true
            } else if (num == -1) {
                visited[row][col] = true
            }
        }
    }

    print(bfs())
}

fun bfs(): Int {
    var count = 0

    q.add(Pair(-1, -1))
    while (q.isNotEmpty()) {
        val cur = q.removeFirst()
        val curRow = cur.first
        val curCol = cur.second

        if (curRow == -1 && curCol == -1) {
            count++
            if (q.isNotEmpty()) q.add(Pair(-1, -1))
            continue
        }

        for (i in 0 until 4) {
            val newRow = curRow + dy[i]
            val newCol = curCol + dx[i]

            if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= m) continue
            if (visited[newRow][newCol]) continue

            farm[newRow][newCol] = 1
            visited[newRow][newCol] = true
            q.add(Pair(newRow, newCol))
        }
    }

    // BFS를 다 돌았는데 안 익은 토마토가 있는지 확인
    farm.forEach {
        it.forEach { num ->
            if (num == 0) return -1
        }
    }
    return count -1
}