[백준] 2573번: 빙산 - Kotlin[코틀린]

문제

 

2573번: 빙산

 

---

풀이

 

 BFS나 DFS를 활용해 풀이하면 된다. 탐색에는 방문을 확인하는 visited 배열과 얼마나 녹을지를 저장하는 melted 배열을 이용한다.

 

 탐색은 빙산을 기준으로 하며 방문 지점이 0보다 클 때  visited 배열에 방문 표시를 하고 이어서 탐색해준다. 0 이하인 경우에는 현재 위치의 melted 배열에 1을 증가해준다.

 

 탐색하는 횟수를 세어 2 이상인 경우에는 빙산이 분리된 것이므로 반복문을 종료하고 시간을 출력해준다. 0인 경우에는 빙산이 분리되지않고 다 녹은 것이기 때문에 0을 출력해준다. 1인 경우에 탐색에서 저장한 melted 배열을 빙산 배열에서 빼주는 것으로 빙산을 녹여준다.

 

---

코드

 

 - DFS

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

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

    val (rows, cols) = br.readLine().split(' ').map { it.toInt() }
    val map = Array(rows){ br.readLine().split(' ').map { it.toInt() }.toIntArray() }

    lateinit var melted: Array<IntArray>
    lateinit var visited: Array<BooleanArray>
    fun dfs(x: Int, y: Int) {
        visited[x][y] = true

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

            if(nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue
            if(visited[nx][ny]) continue

            if(map[nx][ny] <= 0) {
                melted[x][y]++
            } else {
                visited[nx][ny] = true
                dfs(nx, ny)
            }
        }
    }

    var time = 0
    while (true) {
        var cnt = 0 // 탐색 횟수, 빙산의 개수
        melted = Array(rows){ IntArray(cols) }
        visited = Array(rows){ BooleanArray(cols) }

        for(i in 0 until rows) {
            for(j in 0 until cols) {
                if(map[i][j] > 0 && !visited[i][j]) {
                    cnt++
                    dfs(i, j)
                }
            }
        }

        if(cnt > 1) break // 분리된 빙산
        if(cnt == 0) { // 분리되지 않는 빙산
            time = 0
            break
        }

        time++
        for(i in 0 until rows) { // 빙산 녹이기
            for(j in 0 until cols) {
                map[i][j] -= melted[i][j]
            }
        }
    }

    bw.write("$time")
    bw.flush()
    bw.close()
    br.close()
}

 

 - BFS

import java.util.*

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

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

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

    val (rows, cols) = br.readLine().split(' ').map { it.toInt() }
    val map = Array(rows){ br.readLine().split(' ').map { it.toInt() }.toIntArray() }

    lateinit var melted: Array<IntArray>
    lateinit var visited: Array<BooleanArray>
    fun bfs(x: Int, y: Int) {
        val queue: Queue<Point> = LinkedList()
        queue.offer(Point(x, y))
        visited[x][y] = true

        while (queue.isNotEmpty()) {
            val tmp = queue.poll()

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

                if(nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue
                if(visited[nx][ny]) continue

                if(map[nx][ny] <= 0) {
                    melted[tmp.x][tmp.y]++
                } else {
                    visited[nx][ny] = true
                    queue.add(Point(nx, ny))
                }
            }
        }
    }

    var time = 0
    while (true) {
        var cnt = 0
        melted = Array(rows){ IntArray(cols) }
        visited = Array(rows){ BooleanArray(cols) }

        for(i in 0 until rows) {
            for(j in 0 until cols) {
                if(map[i][j] > 0 && !visited[i][j]) {
                    cnt++
                    bfs(i, j)
                }
            }
        }

        if(cnt > 1) break
        if(cnt == 0) {
            time = 0
            break
        }

        time++
        for(i in 0 until rows) {
            for(j in 0 until cols) {
                map[i][j] -= melted[i][j]
            }
        }
    }

    bw.write("$time")
    bw.flush()
    bw.close()
    br.close()
}