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

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

1941번: 소문난 칠공주

 

난이도 : 골드 3
태그 : 수학, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 조합론, 백트래킹

 

 

설명

DFS를 사용해 풀면 되겠네! 라는 생각이 바로 떠올랐지만,

생각해보니 순수 DFS만으로 풀기에는 조금 무리가 있었습니다.

 

결국... 이게 뭐지??? 하는 생각에 태그를 펼쳐봤습니다.

 

그렇습니다. 이 문제는

1. 5 x 5 = 25명의 자리 중 7명을 뽑고(백트래킹),

2. 모든 조합에 대해 이다솜파(S)가 4명 이상인지 확인한 뒤,

3. 모든 학생들의 자리가 이어져 있는지 확인(DFS/BFS 사용)하는 문제였습니다.

자리가 25개밖에 안되니 충분히 시간 안에 통과 가능합니다.

 

 

 

소스코드

data class Node(val x: Int, val y: Int)

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

lateinit var map: Array<CharArray>
val visited = Array(25) { false }
var result = 0

fun main() = with(System.`in`.bufferedReader()) {
    map = Array(5) { readLine().toCharArray() }
    selectSeven(0, 0, 0)
    println(result)
}

// 7개의 자리를 선택
fun selectSeven(idx: Int, cnt: Int, scnt: Int) {
    if (cnt == 7) {
        if (scnt >= 4 && bfs()) result++
        return
    }

    for (i in idx until 25) {
        val x = i / 5
        val y = i % 5
        visited[i] = true
        selectSeven(i + 1, cnt + 1, scnt + if (map[x][y] == 'S') 1 else 0)
        visited[i] = false
    }
}

// 모든 자리가 다 이어져있는지 확인
fun bfs(): Boolean {
    val q = LinkedList<Node>() as Queue<Node>
    for (i in 0 until 25) {
        if (visited[i]) {
            q.offer(Node(i / 5, i % 5))
            break
        }
    }

    val bfsVisited = Array(5) { BooleanArray(5) { false } }
    bfsVisited[q.peek().x][q.peek().y] = true

    var cnt = 1

    while (q.isNotEmpty()) {
        val target = q.poll()

        for (i in 0 until 4) {
            val nx = target.x + dx[i]
            val ny = target.y + dy[i]

            if (nx !in 0 until 5 || ny !in 0 until 5 || !visited[nx * 5 + ny] || bfsVisited[nx][ny]) continue
            q.offer(Node(nx, ny))
            bfsVisited[nx][ny] = true
            cnt++
        }
    }

    return cnt == 7
}

 

selectSeven은 백트래킹으로 25개 자리중 7개를 선택하는 메소드입니다.

이다솜파의 수를 카운팅하는 scnt가 4 이상일 경우에만 모든 자리가 연결되있는지 검사합니다.

 

bfs는 모든 자리가 다 이어져있는지 확인하는 메소드입니다.

selectSeven에서, 선택된 자리는 visited가 true이며, 선택되지 않은 자리는 visited가 false 입니다.

모든 자리를 검사하면서, visited가 true인 자리를 발견하면 큐에 넣고 반복문을 탈출합니다

(시작 좌표를 설정하기 위함입니다)

 

이후의 상, 하, 좌, 우 방향으로 bfs 탐색을 진행하면서,

visited가 true인, 즉, 선택된 7개의 자리의 경우만 탐색을 진행합니다.

bfs가 총 7번 진행된다면, 7개의 모든 자리가 이어져 있는 것으로 볼 수 있습니다.

 

 

후기

조합으로 7개의 자리를 선택한다는 것이 쉽게 떠오르지 않아 고생했던 문제였습니다.

또 하나의 테크닉을 배우게 되네요.