백준 1941 소문난 칠공주 Kotlin (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

문제

총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력

'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

출력

첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

알고리즘 분류

• 수학
• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색
• 조합론
• 백트래킹

풀이

위의 알고리즘 분류로 보면 알 수 있듯이, 여러 가지 시도가 가능한 아주 야무진 문제이다.

본인은 백트래킹으로 풀었고, 3개의 가지치기 조건을 사용했다.

 

1. 다솜파가 후달리는 경우
        if(7-(ns+ny) < 4-ns) continue

2. 이미 탐색한 루트인 경우
        if(resultSet[result or (1 shl i)]) continue

3. 인접하지 않은 경우
        if(result !=0 && !check(r,c)) continue

 

우선 다솜파가 후달리는 경우이다.

7명을 모두 뽑아보지 않고도 위의 식으로 이대로라면 답이 될 수 없어~를 미리 알 수 있다.

예를 들면 다솜파가 2명, 도연파가 3명일 때, 도연파를 더 뽑으면 어떻게 될까~~?

이미 탐색한 루트인 경우도 가지 쳐 줬다.

노드 수가 총 25개이기 때문에 비트 마스킹으로 가능하다.

SSSSSS

Y

Y

위의 경우에서 만약 중복 처리가 제대로 안 된다면 답이 7개가 추가될 것이다.

이를 비트마스킹을 이용해 가지 쳐 주자~

 

마지막으로 인접하지 않은 경우다.

뎁스 0 (첫 번째 사람을 뽑을 때)는 주변에 인접한 사람이 있든 없든 뽑을 수 있으므로 제외하고 나머지 경우에 대해선 주변에 인접한 사람이 없는 경우 가지 쳐 줬다.

인접 확인은 매번 사람을 뽑을 때마다 visited[r][c]에 넣고 해당 탐색이 끝나면 다시 빼는 것으로 현재까지 뽑은 사람들을 체크해주었고,

check함수에서 현재 뽑을 사람의 인접한 위치에 먼저 뽑은 사람이 있는지 확인했다.

fun check(r: Int, c: Int) : Boolean {
    for(i in 0 until 4){
        val nr = r+dir[i][0]
        val nc = c+dir[i][1]
        if(nr !in 0 until 5 || nc !in 0 until 5) continue
        val nIdx = nr*5 + nc
        if(visited[nIdx]) return true
    }
    return false
}

 

이렇게 하면 굉장히 적은 가짓수로 빠르게 통과할 수 있다!

문제 풀 때 주의할 점은 

SSSSS

     Y

     Y 

위의 경우에서 일반적인 그래프 문제처럼 인접 4방향으로 dfs를 돌렸을 때 정상적으로 7명을 뽑을 수 없다는 점이다.

일반적인 그래프 탐색 문제와 조합 문제의 차이를 보여주며, 비트 마스킹, bfs(인접 확인)등 여러 가지 풀이를 고려할 수 있단 점에서 굉장히 좋은 문제라고 생각한다.

 

 

코드

val br = System.`in`.bufferedReader()

val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(-1, 0)
)

lateinit var graph: Array<String>
val resultSet = BooleanArray(1 shl 26)
val visited = BooleanArray(25)
var answer = 0

fun check(r: Int, c: Int) : Boolean {
    for(i in 0 until 4){
        val nr = r+dir[i][0]
        val nc = c+dir[i][1]
        if(nr !in 0 until 5 || nc !in 0 until 5) continue
        val nIdx = nr*5 + nc
        if(visited[nIdx]) return true
    }
    return false
}

fun backTracking( s: Int, y: Int, result: Int) {

    //end
    //7명 채웠고 다솜파가 4명 이상
    if (s + y == 7) {
        //비트마스킹으로 결과 중복 체크
        if( s >= 4) {
            answer++
        }
        return
    }

    for(i in 0 until 25){
        //방문체크
        if(visited[i]) continue

        val r = i/5
        val c = i%5
        var ns = s
        var ny = y
        if(graph[r][c]=='Y'){
            ny++
        }
        else{
            ns++
        }

        //가지치기
        //1. 다솜파가 후달리는 경우
        if(7-(ns+ny) < 4-ns) continue
        //2.이미 탐색한 루트인 경우
        if(resultSet[result or (1 shl i)]) continue
        //3. 인접하지 않은 경우
        if(result !=0 && !check(r,c)) continue
        visited[i] =true
        resultSet[result or (1 shl i)] = true
        backTracking(ns,ny,result or (1 shl i))
        visited[i] = false
    }
}

fun main() = with(System.out.bufferedWriter()) {

    //input
    graph = Array(5) { br.readLine() }
    //solve
    backTracking(0,0,0)
    //output
    write("$answer")
    close()
}