#작성중 백준 9481 스카이스크래퍼 skyscrappers, 백트래킹, dlx

1. 스카이스크래퍼

백준9481-스카이스크래퍼

백준에 있는 문제는 한 라인에 좌우 양쪽 clue가 주어졌을 때 한 라인에서 가능한 경우의 수가 몇 개인지를 찾는 문제다.

입력 예시를 보면 위와 같이 양쪽에서 바라봤을 때 건물이 2개가 보이는 경우, 2가지 경우의 수 가 가능하다.

하지만 이는 sub문제라고는 할 수 있겠지만 한 줄만 따지기 때문에 일반적인 문제는 아니다. 일반적인 스카이스크래퍼의 문제는 2가지 유형으로 나눌 수 있다.

1. 모든 clue가 존재한다.

2. 일부 clue만 존재한다.

 

우리가 고려할 문제는 n*n의 일부 clue만 존재할 때 모든 경우의 정답을 최대한 빠르게 구하는 것이다. 일단 일반적인 경우에 어떻게 풀지 고민해보자.

2. 어떻게 풀 것인가? - 백트래킹을 써야한다.

스카이스크래퍼 참고 블로그

위 참고 블로그에서는 4*4인 문제에서 같은 라인의 양쪽 clue가 모두 존재하고 그 합이 n+1이나 n인 경우 4의 위치를 확정하거나 4가 들어갈 수 있는 위치의 경우의 수를 확정할 수 있다고 설명하고 있다. 굉장히 휴리스틱한 방법이지만 이해를 돕기에 좋은 설명이라서 가져왔다.

하지만 위 방법으로 하다보면 결국 마지막에는 clue가 부족해져서 확정지을 수 있는 위치에 한계가 있고, dfs나 bfs를 이용해서 모든 경우를 탐색해야하는 상황이 올 것이다. 결국 이 문제는 일단 한 번 해보고 조건에 위배되지 않았는지 확인하는 백트래킹을 쓸 수 밖에 없다.

3. DP(Dynamic Programing)로는 못 푸나?

백트래킹 말고 휴리스틱한 방법과 재귀를 잘 활용하여 dp로 풀 수 있는 방법이 없을까 고민했는데

4*4인 경우에 한 라인에서 오른쪽에서 바라봤을 때 3개가 보인다고 하면

제일 오른쪽에서 연속으로 3개가 보이는 것인지, 제일 오른쪽 값이 x로 정해지고 그 왼쪽부터 x보다 큰 녀석들이 2개가 보인다는 것인지 알 수가 없다. 위와 같은 상황에서 principle of optimality(연속된 최적의 선택은 초기 상태, 선택으로 결정된 상태와 무관하게 나머지 선택도 최적이어야 한다. 최적 solution의 일부도 작은 문제의 optimal한 solution이다.)를 만족하는, 구하고자 하는 최적 선택 자체를 정의하기 힘들었고(어떤 기준으로 선택했을 때 건물 높이를 확정지을 수 있는 결과가 나올 수 있는가?) 마땅한 재귀식을 찾을 수 없었다.

4. 백트래킹

백트래킹을 다음과 같이 구현할 수 있다.

4-1. 1~n 대입

한 위치의 값을 정할 건데, 한 위치에서 반복문을 1~n까지 돌면서 하나씩 대입해본다.

위 그림의 경우는 (0,3)의 위치의 값을 정할 것인데 1을 대입해봤는데 같은 라인에 (0,1)에 위치에 1이 이미 있어서 불가능한 상황이라 1 다음 숫자인 2를 대입해보는 상황이다. (0,0)~(0,2)까지 값이 확정된 것이라면 결국 (0,3)에 가능한 숫자는 4일 것이다.

1~n까지 무작위로 대입하고 그 결과가 조건에 위배되는지 확인하는 반복문을 또 돌아야 한다. 확인해야할 조건은 같은 라인에 같은 숫자가 2번 이상 들어갔는지, 대입한 숫자가 clue를 만족하는지 2가지가 되겠다.

4-2. 미리 후보 선정, 후보 대입

미리 불가능한 경우를 지워, 위치 별로 후보들을 만들어 놓고 후보를 하나씩 대입해본다.

아래 그림처럼 clue가 주어져있으면 각 위치에 가능한 후보군들만 적어놓는 상황이다.

위 그림 좌측의 경우 clue가 1이므로 4*4에서 바로 앞에 건물이 하나만 보이는 경우는 4층 건물이 있는 경우 하나 밖에 없다. 비슷하게 우측의 경우도 건물 4개가 보여야 하므로 1~4까지 순서대로 배치될 수 밖에 없다.

그림 좌측처럼 건물이 2개가 보이려면 clue 바로 앞에 위치에는 4층 건물은 무조건 올 수가 없다. 4층이 위치하게 되면 2개가 보이는 것이 아닌 1개가 보이므로 후보에서 4층은 확실하게 배제할 수 있다. 그림 우측의 경우는 똑같이 clue가 2이므로 clue바로 앞에 123의 후보가 들어가야하는데, clue가 4인 경우 때문에 1,2,3,4가 확정된 것이 있으므로 1과 2가 확정된 위치에서 col 방향으로 1과 2가 배제되어, clue 2의 앞이지만 각각 23, 13의 후보를 가지게 된다.

건물이 3개가 보이려면 바로 앞에 위치에는 3층 이상이 올 수가 없어 3과 4가 배제된다.

4-2-1. 후보배제

SIZE가 4인 경우
1->4 // clue가 1일 때 그 바로 앞 칸은 4만 가능
2->4x // clue가 2일 때 그 바로 앞 칸은 4 불가능, 그 다음 칸에 대해서는 모름
3->4x,3x // clue가 3일 때 그 바로 앞 칸은 4,3 불가능, 그 다음 칸에 대해서는 모름
4->1 | 2 | 3 | 4 // 모든 칸이 정해짐

 

SIZE가 5인 경우
1->5
2->5x
3->5x,4x
4->5x,4x,3x
5->1 | 2 | 3 | 4 | 5 // 모든 칸이 정해짐

 

정리해보면 clue의 숫자가 커질 수록 clue 바로 앞 칸에 배제할 수 있는 층이 많아진다. 하지만 바로 앞 칸의 얘기이지 그 너머 칸에 대해서는 보장할 수 없다. 위 그림에서도 clue 3 앞에 1이 선택되면 그 다음 칸 후보 124 중 1이 사라져 24가 될 것이고, clue 3 앞에 2가 선택되면 그 다음 칸 후보 124 중 2가 사라져 14가 될 것이기 때문에 바로 앞 칸이 아닌 그 너머는 확정되지 않은 선택이다.

4-3. 어떤 방법으로 구현할까

4-2의 방법으로 구현할 때 미리 조건에 위배되는 후보들을 "모두 완벽하게" 제외할 수 있다면, 즉 후보들이 불가능한 경우 없이 가능한 경우로만 이루어져 있다면( == dfs의 결과물이 모두 가능한 경우, == 정답이 여러 개) 4-1처럼 후보를 대입 후 조건에 위배되는지 확인하는 반복문을 돌 필요 없이, 후보들을 생성한 후 dfs나 bfs로 모든 경우의 후보를 대입만 하면 정답이 여러 개 나온다.

 

스카이스크래퍼에서는 한 위치의 값을 확정하면 다른 위치의 후보들이 제거되는 영향을 받기 때문에 미리 불가능한 경우를 모두 배제 못 한다고 결론 지었다. 따라서 4-1번과 4-2번의 차이가 없이 하나를 대입해보면 그 선택이 틀렸는지 검증하는 반복문을 무조건 돌아야 한다.

그럼에도 다음과 같은 생각 때문에 4-2번 후보들을 만드는 방식을 채택했다.

 

4-3-1. 1~n을 대입해보는 것 보단 후보배제를 통해서 줄어든 후보들만 대입하는 것이 조합한 경우의 수가 적다. == decision tree에서 자식 노드의 수가 적다. (대입 시도하기 전에 미리 후보를 거르는 작업이 필요하지만)

4-3-2. 가로, 세로에 같은 숫자가 들어갈 수 없어 이를 검사하려면 대입한 위치에 row, col을 다 돌면서 검사해야한다. 하지만 미리 후보들을 만들면 특정위치에 불가능한 값은 후보로 넣지 않기 때문에 후보들끼리만 가로, 세로 위치에 겹치는 값이 있는지 확인하면 반복문을 적게 돌 수 있다. 그런데 한 위치에 대해 값을 대입해보고 그 위치 가로세로 후보들에서 방금 대입해본 숫자를 잘 지워주면 겹치는지 검사할 필요가 없을 것 같다. 이러면 같은 라인에 있는 다른 후보들을 지워주는 작업이 모든 row, col을 도는 것과 차이가 없다.

 

결국 후보를 대입하고, 가로세로 후보를 지우고, clue를 위반하는지 확인하는 방식으로 구현하면 될 것 같다.

5. 후보배제 + 백트래킹 예시 pseudo코드

정리해보면 clue를 통해서 최대한 확정지을 수 있는 위치의 숫자는 확정을 지어주고(clue가 1, 4인 경우 확정), 각 위치에 가능한 후보군을 적어두고 clue가 있는 경우에 불가능한 후보군을 지우고 더 이상 지울 후보군이 없으면 임의의 값을 확정짓는 백트래킹을 시도하는 방법을 생각할 수 있다.

수도코드니까 전체적인 그림만 보자 검증을 안 해봤기 때문에 아래 코드는 논리적으로 틀릴 수 있다.

func 후보지우기(clue바로앞위치, c, candidate) {
    if SIZE == 4 {
        c->candidate[clue바로앞위치]
        1->4
        2->4x
        3->4x,3x
        4->4x,3x,2x
    }
}

func 백트래킹(i, j int, candidate [SIZE][SIZE][]int) (bool, [SIZE][SIZE][]int) {
    if i == SIZE && j == SIZE-1 {
        if clue 만족? {
            return true, candidate
        }
        return false, nil
    }
    for candi := range(candidate[i][j]) {
        확정(i, j, candi, candidate)
        if j == SIZE-1 {
            if finish, ret := 백트래킹(i+1, j); finish {
                return true, candidate
            }
        }
        if finish, ret := 백트래킹(i, j+1); finish {
            return true, candidate
        }
    }
    return false, nil
}

func 확정(i, j, num int, candidate [SIZE][SIZE][]int) {
    // 크로스로 후보에서 num 지우기
    for y:=0; y<SIZE; y++ {
        candidate[y][j]에 num 지우기
    }
    for x:=0; x<SIZE; x++ {
        candidate[i][x]에 num 지우기
    }
    // num만 후보 하나로 남겨두기
    candidate[i][j] = [SIZE][SIZE][]int{ num }
}

func main() {
    var clue [4][SIZE]int
    var candidate [SIZE][SIZE][]int

    clue 입력 받음
    // 후보 1~SIZE 채우기
    for i:=0; i<SIZE; i++ {
        for j:=0; j<SIZE; j++ {
            for k:=1; k<=SIZE; k++ {
                candidate[i][j] = append(candidate[i][j], k)
            }
        }
    }
    // 확정 지을 수 있는 건 확정 지음
    for clue {
        if clue == 1 {
            // 바로 앞 위치 후보 SIZE로 확정
            i,j := clue 바로 앞 위치
            candidate[i][j] = append(candidate[i][j], SIZE)
        } else if clue == SIZE {
            candidate들에 1~SIZE 채우기
        } else if clue + 반대편clue == SIZE + 1 {
            candidate에 SIZE 채우기
        }
    }
    // 후보배제
    for c := range(clue) {
        후보지우기(clue바로앞위치, c, candidate)
    }
    한 칸 빼고 다 찬 숫자 있으면 확정()
    i, j := 확정 안 된 좌상단 위치 찾음()
    if finish, ret := 백트래킹(i, j, candidate); finish {
        끝
    } else {
        답이 없는 경우
    }
}

main의 후보배제 주석 위에 한 칸 빼고 다 찬 숫자 있으면 확정()은 아래와 같은 경우를 얘기한다.

4층 건물의 위치가 3군데 확정 됐으므로 4가 들어갈 수 있는 위치는 한 군데 뿐이다. 이런 경우를 빨리 확정지어 주면 가로세로 후보들이 줄어 든다.

5-1. clue를 적극 활용한 pruning 가지치기

백트래킹을 하면서 중요한 것이 특정 위치에서 값을 대입해보고 그 값이 올바른지 확인하는 과정에서 prune(가지치기)를 얼마나 잘 하느냐

이다. 이렇게 후보를 정해놓고 대입하는 방식에서는 후보를 줄이는 것을 pruning으로 볼 수 있겠다. 후보배제를 pruning의 조건으로 쓸 수 있을 것 같았다.

이 위치에서는 clue가 3이고, 백트래킹 과정에서 1 또는 2가 확정될 수 있다. 만약 1이 확정되었다고 치면 그 위치 가로세로에 있는 후보들에서 1이 제외가 된다. 근데 이 위치에서 아래로 내려다 봤을 때 건물이 3개가 보여야 하는데 1층이라는 건물이 확정지어졌으므로 1층 너머는 2층보다 높은 건물이 2개 보여야 한다. 건물이 2개가 보여야 하므로 2, 4 후보 중에서 4층은 불가능한 후보가 된다.

따라서 위와 같이 후보 4를 지우고 2로 확정지을 수 있다. 후보배제를 clue 너머 건물로 재귀적으로 적용할 수 있는 것이다. clue 바로 앞에 위치에 후보가 확정되지 않았으면 그 위치 너머에는 clue가 영향을 끼칠 수 없었지만, clue 앞이 확정되는 순간 그 너머로 후보배제를 적용할 수 있다. 물론 바로 앞 1칸만 적용 가능하다.

이 방법은 SIZE가 커지면 조금 편리해진다. SIZE==5인 경우를 보면

1~5까지 모든 후보가 있고, 오른쪽에서 바라봤을 때 건물이 4개가 보여야 한다. 맨 오른쪽 건물을 후보 중 하나를 골라 2로 확정지으면, 2 너머 건물들은 3개가 보여야한다. 3개가 보여야 하기 때문에 4, 5층 건물은 올 수가 없고 후보가 줄어든다. 또 어느 순간 백트래킹을 하다가 1, 3 후보 중 1을 선택했다고 하면

1 너머로는 건물이 2개가 보여야 하므로 후보 중 5를 지울 수 있게 된다. 이런 식으로 백트래킹 과정에서 후보를 확정지을 때마다 clue가 점점 다음 위치로 넘어가게 된다.

 

위 수도코드에선 모든 후보가 선택됐을 때만 clue를 만족하는지 확인하기 때문에 이 pruning을 적용하려면 후보를 대입해보고 후보가 대입 된 위치 주변에 넘어온 clue가 있는지 확인할 필요가 있고, 넘어가는 clue를 표현하기 위해서 변수에 어떻게 저장해야할지 고민할 필요가 있다.

6. 백준 풀어보자

후보배제를 적용한 방법으로 백준 9481을 풀어보았다. 아직 5-1 에서 prune을 위한 후보배제는 적용하지 않았고 처음에 clue가 주어진 위치만 후보재베를 했다.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func Confirm(candis [][]bool, ans []int, num, idx, n int) {
	for i := 0; i < n; i++ {
		// 확정된 위치 후보 모두 지우기
		candis[idx][i] = true
		// num 다른 위치들에서 지우기
		candis[i][num-1] = true
	}
	ans[idx] = num
}

// l2r 왼쪽에서 -> 오른쪽 방향으로 커지는가?
func AllConfirm(candis [][]bool, ans []int, l2r bool, n int) {
	num := 1
	switch l2r {
	case true:
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				candis[i][j] = true
			}
			ans[i] = num
			num++
		}
	case false:
		for i := n - 1; i >= 0; i-- {
			for j := 0; j < n; j++ {
				candis[i][j] = true
			}
			ans[i] = num
			num++
		}
	}
}

// 후보배제 clue 1인 경우는 안 들어옴
func RemoveCandi(candi [][]bool, idx, clue, n int) [][]bool {
	for i := 0; i < clue-1; i++ {
		candi[idx][n-1-i] = true
	}
	return candi
}

func isFinish(ans []int) bool {
	for _, a := range ans {
		if a == 0 {
			return false
		}
	}
	return true
}

// clue를 만족하냐
func isFit(ans []int, n, l, r int) bool {
	max := 0
	cnt_l, cnt_r := 0, 0
	for i := 0; i < n; i++ {
		if max < ans[i] {
			max = ans[i]
			cnt_l++
			if max == n {
				break
			}
		}
	}
	max = 0
	for i := n - 1; i >= 0; i-- {
		if max < ans[i] {
			max = ans[i]
			cnt_r++
			if max == n {
				break
			}
		}
	}
	return (l == cnt_l) && (r == cnt_r)
}

func BackTrack(candi [][]bool, ans []int, idx, n, l, r int) (ret [][]int) {
	// // 후보 수가 제일 적은 위치 찾기
	// for i := 0; i < n; i++ {

	// }
	// 확정 안 된 시작위치 찾기
	for i := idx; i < n; i++ {
		if ans[i] == 0 {
			idx = i
			break
		}
	}
	//# 경우의 수가 적은 부분 선택하고, 후보배제 적극 활용해야함
	for j, can := range candi[idx] {
		if !can {
			candi_tmp := make([][]bool, n)
			copy(candi_tmp, candi)
			for i := 0; i < n; i++ {
				candi_tmp[i] = make([]bool, n)
				copy(candi_tmp[i], candi[i])
			}
			ans_tmp := make([]int, n)
			copy(ans_tmp, ans)

			Confirm(candi_tmp, ans_tmp, j+1, idx, n)
			if isFinish(ans_tmp) {
				if isFit(ans_tmp, n, l, r) {
					ret = append(ret, ans_tmp)
				} else {
					return ret
				}
			} else {
				ret = append(ret, BackTrack(candi_tmp, ans_tmp, idx, n, l, r)...)
			}
		}
	}
	return ret
}

func Solve(n, l, r int) int {
	ans := make([]int, n)
	// 1로 set 되면 불가능한 후보, bool default 값이 false니까 모든 후보 가능
	// cadis[pos][candi]
	candiNotPossible := make([][]bool, n)
	for i := 0; i < n; i++ {
		candiNotPossible[i] = make([]bool, n)
	}
	// 확정지을 수 있는 거 확정 짓기
	switch l {
	case 1:
		Confirm(candiNotPossible, ans, n, 0, n)
	case n:
		AllConfirm(candiNotPossible, ans, true, n)
	}
	switch r {
	case 1:
		Confirm(candiNotPossible, ans, n, n-1, n)
	case n:
		AllConfirm(candiNotPossible, ans, false, n)
	}
	if r+l == n+1 {
		Confirm(candiNotPossible, ans, n, l-1, n)
	}
	// 후보배제
	candiNotPossible = RemoveCandi(candiNotPossible, 0, l, n)
	candiNotPossible = RemoveCandi(candiNotPossible, n-1, r, n)
	// 한 칸만 남은 후보 있으면 확정
	for i := 0; i < n; i++ {
		idx := 0
		sum := 0
		for j := 0; j < n; j++ {
			if !candiNotPossible[i][j] {
				sum++
				idx = j
			}
		}
		// 확정 num == idx + 1
		if sum == 1 {
			Confirm(candiNotPossible, ans, idx+1, i, n)
		}
	}

	candi_tmp := make([][]bool, n)
	copy(candi_tmp, candiNotPossible)
	for i := 0; i < n; i++ {
		candi_tmp[i] = make([]bool, n)
		copy(candi_tmp[i], candiNotPossible[i])
	}
	ans_tmp := make([]int, n)
	copy(ans_tmp, ans)

	ret := BackTrack(candi_tmp, ans_tmp, 0, n, l, r)
	// for _, re := range ret {
	// 	fmt.Println(re)
	// }
	return len(ret) % 1000000007
}

func main() {
	for {
		reader := bufio.NewReader(os.Stdin)
		bytes, _, _ := reader.ReadLine()
		line := string(bytes)
		strs := strings.Fields(line)
		nums := [3]int{}
		for i := 0; i < 3; i++ {
			nums[i], _ = strconv.Atoi(strs[i])
		}
		if nums[0] == nums[1] && nums[1] == nums[2] && nums[2] == 0 {
			break
		}
		fmt.Println(Solve(nums[0], nums[1], nums[2]))
	}
}

백준문제의 go 실행환경 자체가 문제가 있는지 런타임에러가 떴다. (내가 작성한 testcase에서는 안 떴음)

c로 코드를 바꾸어 대시 제출해보았다.

#include <stdio.h>
#include <stdlib.h>

#define BOOL

// 사이즈 n인 candidate에서 idx에 위치에 num로 답 확정
void confirm(BOOL int **const candidate, int *const answer, int num, int idx, int n)
{
	for (int i=0; i<n; i++)
	{
		// 확정된 위치 후보 모두 지우기
		candidate[idx][i] = 0;
		// 다른 위치들에서 num 지우기
		candidate[i][num-1] = 0;
	}
	answer[idx] = num;
}

// clue가 1이라서 answer확정
// l2r 왼쪽에서 -> 오른쪽 방향으로 커지는가?
void all_confirm(int *const answer, BOOL int l2r, const int n)
{
	int num = 1;
	// 왼쪽 -> 오른쪽
	if (l2r)
		for (int i=0; i<n; i++)
			answer[i] = num++;
	// 오른쪽 -> 왼쪽
	else
		for (int i=n-1; i>=0; i--)
			answer[i] = num++;
}

void clean_up(BOOL int **candidate, int *const answer, const int n)
{
	for (int i=0; i<n; i++)
		free(candidate[i]);
	free(candidate);
	free(answer);
}

// 사이즈 n인 candidate에서 clue가 idx에 있을 때 후보 지움
// clue가 1, n인 경우는 이미 걸려져서 안 들어옴
// n == 4 일 때
// 2->4x // 적어도 2개가 보여야 하니까 4층 건물은 못 옴, clue가 2일 때 그 바로 앞 칸은 4 불가능, 그 다음 칸에 대해서는 모름
// 3->4x,3x // clue가 1일 때 그 바로 앞 칸은 4,3 불가능, 그 다음 칸에 대해서는 모름
// n == 5 일 때
// 2->5x
// 3->5x,4x
// 4->5x,4x,3x
void remove_candidate(BOOL int **const candidate, int idx, int clue, const int n)
{
	for (int i=0; i<clue-1; i++)
		candidate[idx][n-1-i] = 0;
}

BOOL int **copy_candidate(BOOL int **const candidate, const int n)
{
	BOOL int **ret = malloc(sizeof(int*) * n);
	for (int i=0; i<n; i++)
	{
		ret[i] = malloc(sizeof(int) * n);
		for (int j=0; j<n; j++)
			ret[i][j] = candidate[i][j];
	}
	return (ret);
}

int *copy_answer(int *const answer, const int n)
{
	int *ret = malloc(sizeof(int) * n);
	for (int i=0; i<n; i++)
		ret[i] = answer[i];
	return (ret);
}

BOOL int is_finish(int *const answer, const int n)
{
	for (int i=0; i<n; i++)
		if (answer[i] == 0)
			return (0);
	return (1);
}

// clue를 만족하냐
BOOL int is_fit(int *const answer, const int n, int l, int r)
{
	int max = 0;
	int cnt_l = 0, cnt_r = 0;
	for (int i=0; i<n; i++)
	{
		if (max < answer[i])
		{
			max = answer[i];
			cnt_l++;
			if (max == n)
				break;
		}
	}
	max = 0;
	for (int i=n-1; i>=0; i--)
	{
		if (max < answer[i])
		{
			max = answer[i];
			cnt_r++;
			if (max == n)
				break;
		}
	}
	return ((l == cnt_l) && (r == cnt_r));
}

int backtrack(BOOL int **const candidate, int *const answer, int idx, const int n, int l, int r)
{
	//# 후보 수가 제일 적은 위치 찾게 바꿔야 함
	// 확정 안 된 시작위치 찾기
	for (int i=0; i<n; i++)
		if (answer[i] == 0)
		{
			idx = i;
			break;
		}
	int ret = 0;
	//# 경우의 수가 적은 부분 선택하고, 후보배제 적극 활용하도록 바꿔야 함
	for (int j=0; j<n; j++)
	{
		if (candidate[idx][j])
		{
			BOOL int **tmp_candidate = copy_candidate(candidate, n);
			int *tmp_answer = copy_answer(answer, n);

			confirm(tmp_candidate, tmp_answer, j+1, idx, n);
			if (is_finish(tmp_answer, n))
			{
				if (is_fit(tmp_answer, n, l, r))
					ret += 1;
				else
					return (ret);
			}
			else
				ret += backtrack(tmp_candidate, tmp_answer, idx, n, l, r);

			clean_up(tmp_candidate, tmp_answer, n);
		}
	}
	return (ret);
}

int solve(const int n, int l, int r)
{
	int *answer = malloc(sizeof(int) * n);
	for (int i=0; i<n; i++)
		answer[i] = 0;
	// 1로 set되면 가능한 후보, 처음에 다 가능하다고 가정
	// bool : candidate[pos][candi]
	BOOL int **candidate = malloc(sizeof(int*) * n);
	for (int i=0; i<n; i++)
	{
		candidate[i] = malloc(sizeof(int) * n);
		for (int j=0; j<n; j++)
			candidate[i][j] = 1;
	}
	// 확정지을 수 있는 거 확정 짓기
	if (l == 1)
		confirm(candidate, answer, n, 0, n);
	else if (l == n)
	{
		all_confirm(answer, BOOL 1, n);
		clean_up(candidate, answer, n);
		return (1);
	}
	if (r == 1)
		confirm(candidate, answer, n, n-1, n);
	else if (r == n)
	{
		all_confirm(answer, BOOL 0, n);
		clean_up(candidate, answer, n);
		return (1);
	}
	if (r + l == n + 1)
		confirm(candidate, answer, n, l-1, n);
	// 후보배제
	remove_candidate(candidate, 0, l, n);
	remove_candidate(candidate, n-1, r, n);
	// 한 칸만 남은 후보 있으면 확정
	for (int i=0; i<n; i++)
	{
		int idx = 0;
		int sum = 0;
		for (int j=0; j<n; j++)
		{
			if (candidate[i][j])
			{
				sum++;
				idx = j;
			}
		}
		// 확정 num == idx + 1
		if (sum == 1)
			confirm(candidate, answer, idx+1, i, n);
	}

	BOOL int **tmp_candidate = copy_candidate(candidate ,n);
	int *tmp_answer = copy_answer(answer, n);
	int length = backtrack(candidate, answer, 0, n, l, r);
	clean_up(candidate, answer, n);
	clean_up(tmp_candidate, tmp_answer, n);
	return (length);
}

int main(void)
{
	int n, l, r;

	while (1)
	{
		scanf("%d %d %d", &n, &l, &r);
		if (n == l && l == r && r == 0)
			break;
		printf("%d\n", solve(n, l, r));
	}
}

분기마다 후보배열을 새로 만들어서 복사하는 방법 때문에 메모리 초과가 뜬다.

일단 메모리 문제 때문에 후보를 써놓고 하는 방법으로는 풀 수 없는 것 같아 1~n 반복을 시도해봤다.

#include <stdio.h>
#include <stdlib.h>
#define BOOL

// 숫자가 1개만 들어갔냐 앞에서부터 순서대로 넣기 떄문에 뒤에는 볼 필요 없음
BOOL int is_onehot(int *const answer, const int idx)
{
	for (int i=0; i<idx; i++)
	{
		if (answer[idx] == answer[i])
			return (0);
	}
	return (1);
}

// clue를 만족하냐
BOOL int is_fit(int *const answer, const int n, int l, int r)
{
	int max = 0;
	int cnt_l = 0, cnt_r = 0;
	for (int i=0; i<n; i++)
	{
		if (max < answer[i])
		{
			max = answer[i];
			cnt_l++;
			if (max == n)
				break;
		}
	}
	max = 0;
	for (int i=n-1; i>=0; i--)
	{
		if (max < answer[i])
		{
			max = answer[i];
			cnt_r++;
			if (max == n)
				break;
		}
	}
	return ((l == cnt_l) && (r == cnt_r));
}

// idx위치 후보 선택
int backtrack(int *const answer, int idx, const int n, int l, int r)
{
	int ret = 0;
	for (int num=1; num<=n; num++)
	{
		answer[idx] = num;
		if (!is_onehot(answer, idx))
			continue;
		if (idx == n-1)
		{
			if (is_fit(answer, n, l, r))
			{
				// for (int i=0; i<n; i++)
				// 	printf("%d ", answer[i]);
				// printf("\n");
				ret += 1;
			}
			else
				return (ret);
		}
		else
			ret += backtrack(answer, idx+1, n, l, r);
	}
	return (ret);
}

int solve(const int n, int l, int r)
{
	int *answer = malloc(sizeof(int) * n);
	for (int i=0; i<n; i++)
		answer[i] = 0;
	int length = backtrack(answer, 0, n, l, r);
	free(answer);
	return (length);
}

int main(void)
{
	int n, l, r;

	while (1)
	{
		scanf("%d %d %d", &n, &l, &r);
		if (n == l && l == r && r == 0)
			break;
		printf("%d\n", solve(n, l, r));
	}
}

시간초과가 뜬다. 메모리를 잡아먹지 않으면서 빠르게 백트래킹할 수 있는 방법이 있나 찾아봐야 겠다는 생각이 들었다.

7. 스도쿠랑 비슷한데? dlx

백준2580-스도쿠

가능한 후보를 만들어 내어 대입해보는 것이 스도쿠를 푸는 것과 굉장히 유사하다는 생각이 들어 스도쿠 풀이법을 검색했다. 스도쿠를 exact cover를 찾는 문제로 치환하여 knuth's x 알고리즘으로 dlx(dancing link x)를 구현하여 풀 수 있다고 한다.

스도쿠 dlx 참고 블로그

knuth's x 알고리즘, dlx 참고 글

knuth's 알고리즘 자체는 exact cover를 찾는 문제를 그냥 백트래킹을 하는 것인데 이를 dancing link(네방향 linked list)로 구현하여 반복문을 도는 시간을 줄이는 방법이라는 것이다.

논문을 읽어보면 doubly linked list에서 원소 x를 제거한 후 x를 알고있을 때(변수에 저장해 놓고) x를 다시 link list에 집어 넣는 방법을 backtracking에서 사용하기 용이하며 이를 dancing link라고 부르고 있다.

 

논문에서 cover라고 만 하고 명확한 의미가 안 와닿았었는데

cover란 현재 col의 row들이 다른 col에 발을 뻗고 있을 때 다른 col에서 이 row에 접근하지 못하게 막는 과정이라 할 수 있다. cover를 하고나면 현재 col을 가지고 있어야만 row에 접근할 수 가 있다. 현재 col의 row들 중에서 하나를 확정할 것이기 때문에 미리 cover를 하고서 row를 고르는 것이다. 모든 col에서 row를 확정 짓지 않았는데 col의 size가 0이면 겹치는 선택지를 골랐다는 뜻이므로 잘못된 선택이라는 것이다.

그림을 보면서 설명하면

위 그림에서 A col 먼저 row를 선택하기로 했다고 하면, 2나 4 row중에 선택을 하기 전에 A col을 cover한다.

A col의 좌우를 없애주고, A에 연결된 row인 2와 4에 연결된 node들의 위아래를 없애준다.

먼저 2와 연결된 위아래를 없애주고

4와 연결된 위아래를 없애준다.

이렇게 되면 다른 col에서는 A col과 관련된 2와 4 row에 접근을 할 수가 없게 되고 오직 A col에서만 2와 4 row에 접근할 수 있게 된다. 이를 A col을 cover 했다고 한다. A col의 좌우도 없애주었기 때문에 다른 col에서 부터 시작했을 때도 A에서 무언가 row를 확정지었다는 것을 알 수 있다.

이런식으로 다른 col에서 A col과 관련된 node에 접근할 수 없게하는 cover가 완료되고, 이제 A col에서 2와 4중에 어떤 노드를 확정 지을 것인지 선택하면 된다. (코드흐름 안에서 A col과 관련된 변수를 아직 가지고 있기 때문에 우리는 A col에서 시작하는 접근이 가능함)

 

2 row를 선택했다고 하자. 2 row는 ADG로 이루어져 있는데, 2 row를 선택했으면 나중에 DG를 선택하면 안 된다. 2 row와 연결된 node 들의 col들인 D와 G를 cover하면 그게 가능해진다. D 먼저 cover한다고 하면

D의 좌우도 끊어주고, D col과 연결된 row들의 좌우 node의 위아래를 끊어준다.

이미 A를 cover하면서 2 row와 4 row에 연결된 node들의 위아래가 끊어졌기 때문에

D에서 2, 4에 중복된 처리를 할 필요 없이 바로 6으로 넘어가서 D와 연관된 node들을 다른 col에서 못 보게 끊어준다. A에서 2 row를 선택한 순간 D를 선택한 것이므로 D와 관련된 선택지들을 없애주는 것이다.

 

G도 A에서 2 row를 선택한 순간 선택된 것이므로 G도 cover해준다.

그림을 보고 지금 상황을 해석해보면 ADG col에서 row가 선택이 되었고, BCEF의 선택지가 남은 상황이다. B는 선택지가 3 row 1개로 제일 적으므로 B col에서 row를 골라주자, B col에서 row를 고르면 다른 col에서는 볼 수 없어야 하기 때문에

선택하기 전에 미리 B col을 cover해줘야 한다. B col을 cover하면

위 처럼되고 이제 3 row를 선택할 수 있게 된다.

3 row를 선택하자. 3 row에 있는 node 들의 col을 cover 해준다. (3 row에서 C col으로 바로 접근할 수 없는 것 처럼 그려 놨지만 논문을 읽어보면 각 node에서는 각자의 col으로 바로 접근할 수 있다.)

C col 을 cover하게되면 아래와 같고

C를 커버하고 나면 F는 연결된 node가 없어서 cover가 안될 거 같지만 cover와 선택하는 과정은 다르기 때문에 그냥 cover가 된다.

F col을 cover하고 나면 연결된 node는 없지만 F col 좌우가 끊어지게 된다.

아직 E col은 row를 선택하지 않았는데 모든 node와의 연결이 끊어져 선택지가 없어지게 된다. 이러면 exact cover를 찾을 수가 없으므로 backtrack을 시작한다.

 

여태까지 선택지를 정리하면 다음과 같다

 

A col에서 row 선택하기로 정함 -> A col cover

A col에서 2 row 선택 -> 2 row랑 연결된 DG col cover

B col에서 row 선택하기로 정함 -> B col cover

B col에서 3 row 선택 -> 2 row랑 연결된 CF col cover

하나 남은 E col에 연결된 node가 없음 -> backtrack

 

중요한 건 어디 까지 선택을 되돌리냐는 거다. 논문에서 말하기는 어느 col에서 row를 선택하기로 정하는 것은 deterministic 한 것이고, 한 col에서 row를 선택하는 것은 non-deterministic한 것이므로, row를 선택하는 과정까지 되돌리게 된다.

마지막 선택이었던 B col에서 3을 선택하기 전 위치로 되돌리면 B col에서 3 row 말고는 선택지가 없으므로 더 이전인 A col에서 2 row를 선택하기 전 지점으로 돌아간다. (결국 맨 처음)

이번엔 A col에서 2 row를 고르지 않고 4 row를 고른다.

4 row를 고르기 전에 A col을 먼저 cover하고

4 row를 선택해서, 4 row와 연결된 node들의 col인 D도 cover하면 다음처럼 된다.

이제 어떤 col에서 row를 선택할지 col을 골라야 한다.

논문에서는 이 때 연결된 node 수 == size가 작은 col을 고르는게 경우의 수가 줄어든다고 한다. (prune이 되는 것 같다.)

그림에서는 E col의 size가 작아보이므로 E에서 row를 선택할 거기 때문에 E col을 cover하자

E col에서 row 선택지가 1 row 하나이므로 1 row와 관련있는 node 들의 col인 CF를 커버해준다.

선택 안 된 col이 BG가 남았는데 B col에서 row를 선택하기로 하고 B col을 cover 하자

B col에서 5 row를 선택하고 5 row와 관련된 node들의 col을 cover해준다. (아까도 말했지만 cover할 때 col의 남은 node의 개수 == size는 선택하는 과정이 아니기 때문에 상관이 없다. 그냥 cover하면 된다.)

모든 col이 선택되었으므로 정답이다. 여태까지 선택했던 415 row가 정답이다.

 

//# 아직 작성 중

 

 

 

다음처럼 어떤 숫자가 선택될지 number와 그 숫자가 어느 위치에 들어갈지 position으로 col으로 정의해서 한 row 당 node가 2개가 들어가도록 했다. 일단 중복되지 않는 선택을 한 후에 그 결과가 clue를 만족하는 지 확인하는 코드를 짰다.

 

백준 체점 결과

8. 1~n 반복, 후보배제 성능비교