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

 

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

2589번: 보물섬

 

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

 

 

1. 설명

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

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

 

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

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

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

 

 

 

2. 소스코드

      

      

      

    
    

      <kotlin />
    
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 탐색을 새롭게 수행하되,

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

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

 

 

 

3. 후기

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

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

그래프는 항상 재밌네요.