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
)