[백준] 1941번: 소문난 칠공주
15019 단어 kotlincombinationBFSBFS
-
조합과 BFS 탐색이 결합된 문제입니다.
-
처음엔 DFS 탐색 또는 BFS 탐색을 통해 Y가 4번 나오면 멈추고 총 7번의 탐색이 일어났을 때 정답 카운트를 높이는 백트래킹을 구현하려고 했지만, 아래와 같은 테스트 케이스는 DFS와 BFS를 통해 해결하지 못하는 한계가 있었습니다.
-
따라서 25개의 학생 중 7명을 선발하고, 7명 모두가 인접하여 존재하는지 확인하는 과정을 BFS 탐색을 통해 문제를 해결하였습니다.
import java.util.*
var answer = 0
val dx = listOf(1, 0, -1, 0)
val dy = listOf(0, 1, 0, -1)
lateinit var seats: MutableList<List<String>>
lateinit var isPrincess: Array<Boolean>
lateinit var selected: Array<Int>
fun main() {
val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()
seats = mutableListOf()
for (i in 0 until 5) {
seats.add(br.readLine().split("").filter { it.isNotBlank() })
}
isPrincess = Array(25) { false }
selected = Array(7) { 0 }
combination(0, 0, 0)
bw.write("$answer")
br.close()
bw.close()
}
fun combination(index: Int, cntTotal: Int, cntS: Int,) {
if(cntTotal == 7) {
if (cntS >= 4) {
if (isAdjacent()) answer++
}
return
}
for(i in index..24) {
isPrincess[i] = true
selected[cntTotal] = i
if (seats[i / 5][i % 5] == "S") combination(i + 1, cntTotal + 1, cntS + 1)
else combination(i + 1, cntTotal + 1, cntS)
isPrincess[i] = false
}
}
fun isAdjacent(): Boolean {
val visited = Array(25) { false }
val queue: Queue<Int> = LinkedList()
queue.add(selected[0])
var cnt = 1
while (queue.isNotEmpty()) {
val curr = queue.poll()
for (i in 0..3) {
val nx = curr / 5 + dx[i]
val ny = curr % 5 + dy[i]
val next = nx * 5 + ny
if (nx !in 0..4 || ny !in 0..4) continue
if (visited[next]) continue
if (!isPrincess[next]) continue
cnt++
visited[next] = true
queue.add(next)
}
}
return cnt == 7
}
Author And Source
이 문제에 관하여([백준] 1941번: 소문난 칠공주), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kldaji/백준-1941번-소문난-칠공주저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)