KO EN

[Kotlin] Korean Coding Test - Baekjun question 3197 - Swan Lake

by 민갤

Back End / Aug 29 2023

Question

Core

Problems with BFS (Breadth-First Search) and Queue

Get input

private var R = 0
private var C = 0

private lateinit var lake: Array<Array<Char>> // Lake
private var waterQueue = ArrayDeque<Pair<Int, Int>>()   // water area
private var swan = Pair(0, 0)   // Waiting Swan Location
private var swanQueue = ArrayDeque<Pair<Int, Int>>()    // the swan area
private lateinit var swanVisible: Array<Array<Boolean>> // Whether the swan visited

/**
 * Initialization
 */
private fun init() {
    System.`in`.bufferedReader().run {
        StringTokenizer(readln()).run {
            R = nextToken().toInt()
            C = nextToken().toInt()
        }

        // Initial state of the lake
        lake = Array(R) { r ->
            val str = StringTokenizer(readln()).nextToken()
            Array(C) { c ->
                // Putting all points in the water queue except the ice sheet
                if (str[c] != ICE_SHEET) waterQueue.add(Pair(r, c))
                // Swan Location
                if (str[c] == SWAN) swanQueue.add(Pair(r, c))
                // lake condition
                str[c]
            }
        }

        // A swan to wait for
        swan = swanQueue.removeFirst()
        // Whether the swan visited
        swanVisible = Array(R) { Array(C) { false } }
    }
}

Move swan

private const val WATER = '.'
private const val ICE_SHEET = 'X'
private const val SWAN = 'L'

private lateinit var lake: Array<Array<Char>>
private var swan = Pair(0, 0)   // Waiting Swan Location
private var swanQueue = ArrayDeque<Pair<Int, Int>>()    // the swan area
private lateinit var swanVisible: Array<Array<Boolean>> // Whether the swan visited

// ice melting distance
private val meltingDistance = arrayOf(Pair(-1, 0), Pair(0, -1), Pair(1, 0), Pair(0, 1))

private var flag = false

/**
 * Moving the swan
 * - Start from the swan position to be moved
 * - Completion of calculation if the current position matches the waiting swan position
 * - If the adjacent direction (except diagonal) is ice, put it back in the next queue or in the swan queue for re-exploration
 * - However, to prevent swans from searching repeatedly, visit points should be saved separately (swan visible) and the points already visited should be skipped
 */
private fun moveSwan() {
    val nextQueue = ArrayDeque<Pair<Int, Int>>()

    while (swanQueue.isNotEmpty() && !flag) {
        val moveSwan = swanQueue.removeFirst()
        // Meeting a swan
        if (swan.first == moveSwan.first && swan.second == moveSwan.second) {
            flag = true
            break
        }
        meltingDistance.forEach move@{
            val moveRow = moveSwan.first + it.first
            val moveCol = moveSwan.second + it.second

            if (!isMove(moveRow, moveCol)) return@move
            if (swanVisible[moveRow][moveCol]) return@move
            swanVisible[moveRow][moveCol] = true

            if (lake[moveRow][moveCol] == ICE_SHEET) nextQueue.add(Pair(moveRow, moveCol))
            else swanQueue.add(Pair(moveRow, moveCol))
        }
    }

    swanQueue = nextQueue
}

/**
 * Overflow protection
 */
private fun isMove(row: Int, col: Int): Boolean {
    return row > -1 && col > -1 && row < R && col < C
}

Melting ice sheets

private const val WATER = '.'
private const val ICE_SHEET = 'X'
private const val SWAN = 'L'

private lateinit var lake: Array<Array<Char>>
private var waterQueue = ArrayDeque<Pair<Int, Int>>()   // Water area (ice plate turned into water)

// ice melting distance
private val meltingDistance = arrayOf(Pair(-1, 0), Pair(0, -1), Pair(1, 0), Pair(0, 1))

/**
 * melting ice sheets
 * - Starting with the initial water
 * - If the adjacent direction (excluding diagonal) is ice, melt the point and place it in a melt queue. (Perform BFS)
 * - update the melt queue to the water queue
 * - Each time the function is executed, BFS will be performed from the point where the search was previously stopped (water where the ice sheet melted)
 * - Existing water is not visited again after searching, so the number of searches can be reduced. (Remove Duplicate Discovery)
 */
private fun meltIce() {
    // an ice sheet melted into water
    val meltQueue = ArrayDeque<Pair<Int, Int>>()

    // Existing water area
    while (waterQueue.isNotEmpty()) {
        val currNode = waterQueue.removeFirst()

        // melting ice sheets adjacent to water
        meltingDistance.forEach move@{
            val moveRow = currNode.first + it.first
            val moveCol = currNode.second + it.second

            if (!isMove(moveRow, moveCol)) return@move
            if (lake[moveRow][moveCol] != ICE_SHEET) return@move

            lake[moveRow][moveCol] = WATER
            meltQueue.add(Pair(moveRow, moveCol))
        }
    }

    // newly created water point by melting
    waterQueue = meltQueue
}

/**
 * Overflow protection
 */
private fun isMove(row: Int, col: Int): Boolean {
    return row > -1 && col > -1 && row < R && col < C
}

Practice

fun main() {
    init()

    var day = 0
    while (true) {
        // moving the swan
        moveSwan()
        // When swans meet, it's over
        if (flag) break
        // melting ice sheets
        meltIce()
        // Increase Date
        day++
    }

    println(day)
}