[백준 2589번] [Kotlin] 보물섬

 

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

2589번: 보물섬

 

난이도 : 골드 5
태그 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색

 

 

설명

같은 육지 내에서 최단 경로로 이동했을 때, 거리가 가장 긴 경로를 찾는 문제입니다.

BFS를 응용하여 풀 수 있을 것 같은데요.

 

그럼, 같은 육지 내 겨올가 최대가 되는 경우는 어떻게 찾을 수 있을까요?

단순히 육지의 모든 점에서 BFS를 수행하면 됩니다.

가로, 세로의 크기가 최대 50밖에 되지 않기 때문에 충분히 시간 안에 통과가 가능합니다.

 

 

 

소스코드

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

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val map = Array(n) { readLine().toCharArray() }

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

    repeat(n) { x ->
        repeat(m) { y ->
            if (map[x][y] == 'W') return@repeat

            val visited = Array(n) { IntArray(m) { 0 } }

            val queue = LinkedList<Pair<Int, Int>>() as Queue<Pair<Int, Int>>
            queue.add(Pair(x, y))
            visited[x][y] = 1

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

                for (i in 0 until 4) {
                    val nx = target.first + dx[i]
                    val ny = target.second + dy[i]

                    if (nx !in 0 until n || ny !in 0 until m || visited[nx][ny] != 0 || map[nx][ny] == 'W') continue
                    queue.add(Pair(nx, ny))
                    visited[nx][ny] = visited[target.first][target.second] + 1

                    if (visited[nx][ny] > max) max = visited[nx][ny]
                }
            }
        }
    }

    println(max - 1)
}

 

 

육지의 모든 점에서 BFS 탐색을 새롭게 수행하되,

매번 경로의 최댓값을 갱신하는 방식으로 진행되고,

최종적으로 최댓값을 출력합니다.

 

 

 

후기

처음에 BFS에 다이나믹 프로그래밍을 섞어 풀어야 하나 싶긴 했지만,

범위를 보고 안심하며 브루트포스 + BFS로 풀었습니다.

그래프는 항상 재밌네요.