문제

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

내 생각

BFS와 브루트포스가 섞인 문제이다. 결국 L 즉, 땅지역에서는 무조건 탐색을 진행해 최대 거리를 알아내야 하는 것이 핵심이다.

BFS를 하기 위해선 Queue에 x좌표 y좌표를 담아두고 다음 탐색을 진행하지만, 이 경우 최대 경로를 계산하는 문제이므로 좌표값 외에 각 탐색할 때마다의 거리값 또한 가지고 있어야한다.

그래서 Triple 자료형을 사용해서 구현을 진행했다.

깨달은 점

BFS DFS와 같은 완전탐색을 진행할 때, 계산해야하는 경우가 있다면 Queue에 담아두고서 그 값으로 계산해야 한다.

코드

class BOJ2589 {
    var height = 0
    var width = 0
    private lateinit var board: MutableList<CharArray>
    private val dx = listOf(1, -1, 0, 0)
    private val dy = listOf(0, 0, 1, -1)
    fun solve() {
        val (tempH, tempW) = readLine()!!.split(' ').map { it.toInt() }
        var ans = 0

        height = tempH
        width = tempW
        board = MutableList(height) { CharArray(width) }.map {
            readLine()!!.toCharArray()
        }.toMutableList()

        for (i in 0 until height) {
            for (j in 0 until width) {
                if(board[i][j] == 'L'){
                    ans = max(ans,bfs(i, j))
                }
            }
        }

        println(ans)
    }

    fun bfs(x: Int, y: Int): Int {
        val queue: Queue<Triple<Int, Int, Int>> = LinkedList()
        val visited = MutableList(height) { BooleanArray(width) { false } }
        var dist = 0
        queue.add(Triple(x, y, 0))
        visited[x][y] = true
        while (!queue.isEmpty()) {
            val cursor = queue.poll()
            for (i in 0 until 4) {
                val nx = cursor.first + dx[i]
                val ny = cursor.second + dy[i]
                val tempDist = cursor.third
                if (nx < 0 || ny < 0 || nx >= height || ny >= width) continue
                if (board[nx][ny] == 'L' && !visited[nx][ny]) {
                    queue.add(Triple(nx, ny, tempDist + 1))
                    visited[nx][ny] = true
                    dist = max(dist, tempDist + 1)
                }
            }
        }
        return dist
    }
}