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

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

2589번: 보물섬

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

 

 

설명

보물의 위치는 한 섬에서 서로 가장 먼 두 점에 있습니다.

최단경로가 아닌, 최장 경로를 찾는 문제인 셈이지요.

 

어떻게 구해야 하나 싶었는데,

가로, 세로의 길이가 각각 50이하인 것을 보고,

브루트포스적으로 접근하여 육지의 모든 점에서 BFS를 돌려 해당 점에서 가장 먼 점을 찾은 뒤,

가장 먼 점을 계속 갱신해주는 방법으로 접근하였습니다.

 

 

 

소스코드

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로 해결했던 문제였습니다.