[백준/BOJ] 17086번: 아기 상어2

문제

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

17086번: 아기 상어 2

해설

처음에는 0인 모든 지점에서 bfs를 수행시켜 가장 가까운 상어까지의 거리를 구하려고 하였다.

하지만 왠지 모르게 계속해서 답이 아닌 값이 나와 다른 방법으로 접근을 해보자는 생각을 했다.

여기서 생각해낸 것은 각 상어가 있는 지점부터 다른 상어가 있는 지점까지를 구해보자였다.

즉, 모든 상어가 있는 지점을 큐에 넣어준 후 bfs를 수행시키는 것이다. 과정은 다음과 같다.

빈 칸은 0으로 두고 1이 있는 칸은 상어가 있는 칸이라고 하자.

우선 상어가 있는 칸을 모두 큐에 넣어준다.

이와 동시에 상어가 있는 칸을 방문 처리해주고, 숫자를 0으로 변경시켜준다.

즉, 큐에는 (0, 2), (2, 0), (5, 4)가 있다.

우선 각 상어의 점에서부터 각 8방향으로 한칸씩 나아간다.

배열을 map이라 했을 때 map[nextY][nextX] = map[curY][curX] + 1이 된다.

bfs를 한번 수행했을 때 다음과 같이 되는 것이다.

이 때 방문한 칸에 대한 방문 처리를 잊으면 안된다.

결론적으로 bfs를 끝냈을 때는 다음과 같이 된다.

즉, 안전 거리가 가장 큰 값은 이 배열에서의 가장 큰 값이 된다.

이는 bfs를 모두 수행시킨 후 모든 배열을 돌며 가장 큰 값을 찾아도 되고,

전역변수로 안전 거리를 선언해놓은 후 더 큰 값이 나올 때마다 갱신해주면 된다.

사람마다 코드를 짜는 방법이 다를 수 있으므로, 더 편한 것으로 하면 된다.

코드

import java.util.*
import kotlin.math.max

private var n = 0
private var m = 0
private var maxSafeArea = 0
private lateinit var map: Array<IntArray>
private lateinit var visited: Array<BooleanArray>
private val que: Queue<Pair<Int, Int>> = LinkedList()
private val dx = arrayListOf(1, 1, 1, -1, -1, -1, 0, 0)
private val dy = arrayListOf(1, -1, 0, 1, -1, 0, 1, -1)

fun main() = with(System.`in`.bufferedReader()) {
    val size = readLine().split(" ").map { it.toInt() }
    n = size[0]
    m = size[1]

    map = Array(n) { IntArray(m) }
    visited = Array(n) { BooleanArray(m) }

    repeat(n) { i ->
        val state = readLine().split(" ").map { it.toInt() }
        repeat(m) { j ->
            map[i][j] = state[j]
        }
    }

    repeat(n) { i ->
        repeat(m) { j ->
            if(map[i][j] == 1) {
                que.add(Pair(i, j))
                map[i][j] = 0
                visited[i][j] = true
            }
        }
    }

    bfs()

    println(maxSafeArea)
}

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

        for(i in 0 until 8) {
            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(!isCondition(nextY, nextX)) continue

            visited[nextY][nextX] = true
            map[nextY][nextX] = map[curY][curX] + 1
            que.add(Pair(nextY, nextX))

            maxSafeArea = max(maxSafeArea, map[nextY][nextX])
        }
    }
}

private fun isCondition(y: Int, x: Int): Boolean = y in 0 until n && x in 0 until m && !visited[y][x]