[BOJ] 15684번 : 사다리 조작(Go, Golang)

문제 링크 : 백준 15684번

[문제 접근]

가로선을 놓을 수 있는 모든 경우의 수를 해봐야한다.(나는 조합을 사용했다.)

1. arr배열은 0이면 가로선이 없는 것, 1이면 오른쪽으로 가로선이 있는 것, 2면 왼쪽으로 가로선이 있는 것으로 설정해주었다.
2. check함수에 들어가기전 아무것도 하지 않아도 정답일 경우를 먼저 해준다.
3. check함수에 들어가서 조합을 이용해 탐색해주는데 무조건 오른쪽으로 가로선을 그을 수 있게 탐색한다.
   • arr배열이 0이면서 그 다음 arr배열이 왼쪽으로 가로선을 가지고 있지 않을 때 해당 좌표에 가로선을 그을 수 있다.(n번째 세로선은 어차피 오른쪽으로 가로선을 그을 수 없으므로 n-1까지만 탐색한다.)
4. 조건에 맞으면 가로선을 긋고 search함수에 들어가 i번 세로선의 결과가 i번이 나오는지 확인하고 나오면 ans를 최소값으로 설정해주고 안나오면 계속 마저 탐색한다.
5. 정답이 3을 넘어가면 불가능한 경우와 마찬가지이므로 최대 3까지만 탐색하고 정답이 안나오면 불가능한 경우로 판단해준다.

[소스 코드]

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	r       = bufio.NewReader(os.Stdin)
	w       = bufio.NewWriter(os.Stdout)
	n, m, h int
	arr     [11][300]int
	ans     = -1
)

func check(max int, cnt int, startx int, starty int) {
	if max < cnt {
		return
	}
	for i := starty; i <= h; i++ {
		if i > starty {
			startx = 1
		}
		for j := startx; j <= n-1; j++ {
			if arr[j][i] == 0 && arr[j+1][i] != 1 {
				arr[j][i] = 1
				arr[j+1][i] = 2

				if search() { // 테스트
					if ans == -1 || ans > cnt {
						ans = cnt
					}
				}
				check(max, cnt+1, j, i)

				arr[j][i] = 0
				arr[j+1][i] = 0
			}
		}
	}
}

func search() bool {

	for i := 1; i <= n; i++ {
		start := i
		for j := 1; j <= h; j++ {
			if arr[start][j] == 1 {
				start++
			} else if arr[start][j] == 2 {
				start--
			}
		}
		if start != i {
			return false
		}
	}
	return true
}

func main() {
	defer w.Flush()
	fmt.Fscan(r, &n, &m, &h)
	for i := 0; i < m; i++ {
		var a, b int
		fmt.Fscan(r, &a, &b)
		arr[b][a] = 1   // 오른쪽
		arr[b+1][a] = 2 // 왼쪽
	}

	if search() { // 아무것도 안해도 정답일 때
		fmt.Fprintln(w, 0)
	} else {
		check(3, 1, 1, 1)
		fmt.Fprintln(w, ans)
	}

}