백준 2589 보물섬

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

L은 육지이고 W는 바다인 지도가 주어진다.

육지 영역들 중 두 위치의 거리가 가장 긴 곳 사이의 거리를 구하는 문제이다.

그냥 단순하게 완전탐색을 하면 되는 문제였지만, 개념 공부를 소홀히 해서 실수한 부분이 있기에 작성한다.

처음 풀이를 계획할 때 각 육지 영역에서 트리의 지름을 구하는 방법을 사용하려고 했었다.

그래서 각 육지 영역에서, 아무 위치에서 가장 먼 곳을 구하고 그 위치에서 가장 먼 곳을 구해 거리를 지름으로 여겨 풀이를 시도했다.

하지만 해당 알고리즘은 말 그대로 트리 (순환이 없는)에서만 유효한 알고리즘이리 때문에 순환이 존재하는 그래프에선 정상적으로 작동하지 않을 수 있었다.

대표적으로 아래와 같은 예시를 들 수 있다.

7 7
LLLLLLL
LLLLLLW
LLLLLWW
LLLLLWW
LLLWWWW
LLWWWWW
LWWWWWW

(0, 0)위치에서 트리의 지름 알고리즘을 사용한다면 가장 먼 점은 거리 7로 (3, 4)위치가 돼버린다.

그럼 (3, 4)에서 가장 먼 점은 시작점인 (0, 0)이 된다.

하지만 실제로는 (0, 6)에서 (6, 0)까지 거리인 12가 정답이다.

다시 한번 순환이 존재하는 그래프에선 해당 알고리즘이 동작하지 않음을 기억하자!

import java.util.*

val dirs = intArrayOf(-1, 0, 1, 0, -1)

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (V, H) = readLine().split(' ').map{it.toInt()}
    val map = Array(V){readLine().toCharArray()}

    var ans = 0
    fun getFarthest(r: Int, c: Int){
        val visited = Array(V){BooleanArray(H){false}}
        val queue: Queue<Spot> = LinkedList()
        visited[r][c] = true
        queue.offer(Spot(r, c))

        var areaMaxLen = 0
        while(queue.isNotEmpty()){
            val next = queue.poll()
            areaMaxLen = next.moves

            for(i in 0..3){
                val nextR = next.r + dirs[i]
                val nextC = next.c + dirs[i + 1]
                if(isInside(nextR, nextC, V, H) && !visited[nextR][nextC] && map[nextR][nextC] == 'L'){
                    queue.offer(Spot(nextR, nextC, next.moves + 1))
                    visited[nextR][nextC] = true
                }
            }
        }

        if(ans < areaMaxLen) ans = areaMaxLen
    }

    for(i in 0 until V){
        for(j in 0 until H){
            if(map[i][j] == 'L'){
                getFarthest(i, j)
            }
        }
    }
    print(ans)
}

fun isInside(r: Int, c: Int, V: Int, H: Int): Boolean = r in 0 until V && c in 0 until H

data class Spot(
    val r: Int,
    val c: Int,
    val moves: Int = 0
)