https://www.acmicpc.net/problem/15684
최소한으로 사다리를 추가해 i번째에서 시작하면 i번째에서 끝나도록 만드는 케이스를 찾는 문제이다.
세로선과 가로선의 개수가 주어지고, 가로선을 놓을 수 있는 점선 개수가 주어진다.
즉 기본 사다리 틀이 제공되며, 점선을 선택해 사다리로 바꾸어 보며 조건을 만족하는 경우를 찾는 문제이다.
사다리를 놓을 수 있는 공간은 최대 10 x 30 = 300으로 작은 편이고, 위 문제 사진들에는 나오지 않았지만 사다리가 4개 이상 필요한 경우는 -1로 출력하는 조건을 보아 조합을 통한 완전탐색 문제라 생각했다.
풀이를 시작하기 전 먼저 해야할 작업은 사다리를 나타내는 맵을 어떻게 표시할 것인가? 였다.
나의 경우엔 세로 7 가로 6인 이차원 Boolean 배열을 사용하여 표시하였다.
편의성 때문에 인덱스를 1부터 시작하기 위해 크기를 1씩 늘였으며, Boolean 배열인 이유는 한 점을 기준으로 오른쪽에 사다리를 놓는다 가정했기 때문이다.
위의 사다리 맵 구조를 배열로 나타낸다면 7 x 6의 Boolean Array이며
(1, 1) (5, 1) (3, 2) (2, 3) (5, 4) 위치가 true이고 나머지가 false인 구조라 할 수 있다.
이렇게 나타낸 뒤에, 사다리를 놓을 수 있는 후보들을 추려냈다.
사다리를 놓을 수 있는 빈 공간의 조건은 해당 위치의 양쪽에 사다리가 없어야 한다는 것이다. (일렬로 붙여 놓을 수 없다 했으므로)
그렇게 추려낸 사다리 놓을 장소 후보들로 조합(combination) 알고리즘을 적용한다.
위와 같은 예시가 있으면, 사다리를 놓을 수 있는 장소 후보는 1~4번까지 4개이다.
그럼 조합을 통해 사다리 개수에 따라 후보들을 고른다.
0개 - ()
1개 - (1), (2), (3), (4)
2개 - (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)
3개 - (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)
그리고 위 후보들의 위치에 사다리를 추가한 후 i번째에서 출발해 i번째로 도착하는지 모두 확인한다
여기까지가 첫 번째 시도했던 풀이이다.
실제로 예시 테스트케이스들을 통과했지만, 시간 초과가 났다.
그래서 뭐가 문제일까, 보다가 문제점을 발견했다.
위 후보들 중 (1, 2)와 (1, 2, 3), (1, 2, 4)를 고른 케이스를 잘 보자.
사다리 후보인 1과 2는 가로로 붙어 있어 동시에 선택하는 것이 불가능하다.
하나의 사다리를 고른 후 다음 사다리를 고를 때, 이전에 골랐던 사다리를 남겨 두고 해당 사다리까지 고려해야 한다.
즉, 위 예시에서 2개를 뽑아오는 조합 함수를 호출하면 1번 위치를 고른 뒤에 실제로 1번 위치에 사다리가 존재함을 표시하고 2번 위치를 확인할 때 왼쪽 1번에 사다리가 존재함을 확인하고 고르지 않고 넘어가도록 해야 한다.
이 방법을 통해 만들어지는 조합의 개수를 꽤나 줄여 통과할 수 있었다.
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val (N, M, H) = readLine().split(' ').map{it.toInt()}
val field = Array(H + 1){BooleanArray(N + 1){false}}
val candidates = mutableListOf<Pair<Int, Int>>()
for(i in 1..M){
val (s, e) = readLine().split(' ').map{it.toInt()}
field[s][e] = true
}
for(i in 1..H)
for(j in 1..N)
if(leftLineEmpty(i, j, field) && rightLineEmpty(i, j, N, field)) {
candidates.add(Pair(i, j))
}
for(i in 0..3){
val comb = mutableListOf<List<Pair<Int, Int>>>()
combination(comb, candidates, BooleanArray(candidates.size){false}, 0, i, field, N)
comb.forEach{
if(areSrcAndDestSame(it, N, field)){
print(it.size)
return@with
}
}
}
print(-1)
}
fun leftLineEmpty(i: Int, j: Int, field: Array<BooleanArray>) = j == 1 || (j > 1 && !field[i][j - 1])
fun rightLineEmpty(i: Int, j: Int, N: Int, field: Array<BooleanArray>) =
j == N || j < N && !field[i][j]
fun areSrcAndDestSame(additionalLines: List<Pair<Int,Int>>, N: Int, field: Array<BooleanArray>): Boolean{
additionalLines.forEach {
field[it.first][it.second] = true
}
var flag = true
for(i in 1 until field[0].size){
var x = i
var y = 1
while(y < field.size){
when{
!leftLineEmpty(y, x, field) -> { x--; y++ }
!rightLineEmpty(y, x, N, field) -> { x++; y++ }
else -> y++
}
}
if(i != x){
flag = false
break
}
}
additionalLines.forEach {
field[it.first][it.second] = false
}
return flag
}
fun combination(answer: MutableList<List<Pair<Int, Int>>>, el: List<Pair<Int, Int>>, ck: BooleanArray, start: Int, target: Int
, field: Array<BooleanArray>, N: Int) {
if(target == 0) {
answer.add(el.filterIndexed { index, _ -> ck[index] })
} else {
for(i in start until el.size) {
val y = el[i].first
val x = el[i].second
if(leftLineEmpty(y, x, field) && (x < N && !field[y][x + 1])) {
ck[i] = true
field[y][x] = true
combination(answer, el, ck, i + 1, target - 1, field, N)
ck[i] = false
field[y][x] = false
}
}
}
}위에서 설명한 대로 순서는 다음과 같다.
- Boolean 이차원 배열을 통해 사다리 맵을 나타낸다.
- 현재 위치에서 양 쪽에 사다리가 없는, 후보 위치들을 골라 모은다.
- 0개에서 3개까지, 조합 함수를 통해 사다리 후보들을 선택해서 추가한 뒤 검사한다 (i번째 출발 i번째 도착)
+) 조합 함수에선 사다리 맵에 직접 표시하며 고르고, 현재 맵 기준 양쪽이 빈 공간일 때만 고르도록 한다. - 조건을 만족하는 경우 그 때의 추가한 사다리 개수를 출력한다.
