BOJ2589(보물섬)
문제
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
}
}
Author And Source
이 문제에 관하여(BOJ2589(보물섬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@willow_ryu/BOJ2589보물섬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)