[백준/BOJ] 3197번: 백조의 호수

문제

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

3197번: 백조의 호수

해설

예전에 시도했던 문제인데 시간초과가 나서 포기했던 문제이다.

오늘 와서 다시 도전해 봤는데 역시나 어떻게 해야 시간초과를 해결할 수 있을지 감이 잡히지 않아 결국 구글링을 하여 이해를 하였다.

 

처음에 나는 백조를 움직이고, 물을 녹이고 즉, 2개의 큐만을 사용해 문제를 해결하려 했었다.

이 방법으로는 백조가 계속 모든 맵을 탐험하게 되므로 시간초과가 나게 된다.

 

내가 이해한 방법에서는 큐를 총 4개를 쓴다.

현재 백조의 위치를 담는 큐, 현재 물의 위치를 담는 큐, 다음에 백조가 움직일 수 있는 큐, 다음에 물이 될 큐

 

쉽게 말하면 초기의 맵을 bfs를 통해 탐색했을 때, 백조끼리 만날 수 없다면 우리는 다음으로 얼음이 녹는 위치만 탐색해 주면 된다.

예를 들어 다음의 사진을 보자.

아래 있는 백조가 움직인다하면 다음으로 백조가 갈 수 있는 칸은 원을 친 위치가 되게 된다.

 

이처럼 다음에 움직일 수 있는 칸(즉, 다음에 녹을 칸, 탐색 중 X인 칸)을 다음에 백조가 움직일 수 있는 큐에 저장을 해두고, 다음 bfs에 사용하게 되면 된다.

 

물의 위치를 저장한 큐 또한 같다.

초기 위치의 물의 위치를 저장해두고, bfs를 통해 다음에 녹일 위치만을 또 다른 큐에 저장해 두어 사용하는 것이다.

이를 통해 탐색 범위를 줄일 수 있고, 시간초과를 해결할 수 있었다.

코드

import java.util.LinkedList
import java.util.Queue

private lateinit var map: Array<CharArray>
private lateinit var visited: Array<BooleanArray>
private val dir = arrayOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)
private var waterQueue: Queue<Pair<Int, Int>> = LinkedList()
private var swanQueue: Queue<Pair<Int, Int>> = LinkedList()
private val nextWaterQueue: Queue<Pair<Int, Int>> = LinkedList()
private val nextSwanQueue: Queue<Pair<Int, Int>> = LinkedList()
private var meetSwan = false
private var row = 0
private var col = 0

fun main() {
    val input = readLine()!!.split(" ").map { it.toInt() }
    row = input[0]
    col = input[1]

    map = Array(row) { CharArray(col) }
    visited = Array(row) { BooleanArray(col ) }

    var swan = 0 to 0
    repeat(row) {
        map[it] = readLine()!!.toCharArray()
        for(i in map[it].indices) {
            if(map[it][i] == 'L') swan = Pair(it, i)
            if(map[it][i] != 'X') waterQueue.add(Pair(it, i))
        }
    }

    swanQueue.add(swan)
    visited[swan.first][swan.second] = true

    var day = 0

    while(!meetSwan) {
        swanBfs()
        if(meetSwan) break
        waterBfs()

        swanQueue.addAll(nextSwanQueue)
        waterQueue.addAll(nextWaterQueue)

        nextSwanQueue.clear()
        nextWaterQueue.clear()
        day++
    }

    println(day)
}

private fun swanBfs() {
    while(swanQueue.isNotEmpty()) {
        val cur = swanQueue.poll()
        val curY = cur.first
        val curX = cur.second

        for(i in 0 until 4) {
            val nextY = curY + dir[i].first
            val nextX = curX + dir[i].second

            if(!inRange(nextY, nextX) || visited[nextY][nextX]) continue

            visited[nextY][nextX] = true
            if(map[nextY][nextX] == 'X') nextSwanQueue.add(Pair(nextY, nextX))
            else if(map[nextY][nextX] == '.') swanQueue.add(Pair(nextY, nextX))
            else if(map[nextY][nextX] == 'L') {
                meetSwan = true
                break
            }
        }
    }
}

private fun waterBfs() {
    while(waterQueue.isNotEmpty()) {
        val cur = waterQueue.poll()
        val curY = cur.first
        val curX = cur.second

        repeat(4) { i ->
            val nextY = curY + dir[i].first
            val nextX = curX + dir[i].second

            if(!inRange(nextY, nextX)) return@repeat

            if(map[nextY][nextX] == 'X') {
                map[nextY][nextX] = '.'
                nextWaterQueue.add(Pair(nextY, nextX))
            }
        }
    }
}

private fun inRange(y: Int, x: Int): Boolean = y in 0 until row && x in 0 until col