[백준] 1941번: 소문난 칠공주

문제링크

• 조합과 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
}