백준 15684 사다리 조작 C풀이 - DFS

우리에게 익숙한 사다리 타기 문제이다.

모든 번호가 자기 자신을 뽑도록 만들고 싶다.

주어진 사다리에다가 최대 3개의 가로줄을 그어서 자기 자신을 뽑도록 만들면 성공이지만 3개를 초과해야

할 경우엔 실패로 처리한다. 

물론 주어진 사다리가 그대로 성공한 경우도 있으므로 0개도 답이 될 수 있다.

 

접근 방식은 다음과 같다.

1. 0개부터 최대 3개까지 사다리를 임의로 긋는다.

2. 자기 자신을 가리키는지 확인한다.

3. 1-2를 반복하다가 성공하면 그은 횟수, 실패하면 -1를 리턴한다.

 

해결 방식으로 생각한 것은 다음과 같다.

1. 모든 사다리는 자기 자신으로 돌아와야하기 때문에 가로줄은 세로줄 하나 당 짝수 개가 필요하다.

-> 당연한 얘기지만 홀수가 없는 경우도 케이스로 들어오므로 알고리즘에 반영하기 힘들어서 못했다.

2. 완전탐색으로 모든 부분에 설치해보면서 케이스를 정리한다.

-> 아슬아슬하게 통과(800ms)했다. 중복을 제외하고 수행해야 시간 초과가 나지 않는다.

 

풀이를 실패했었던 원인은 다음과 같다.

1. 모든 경우를 탐색하며 중복제거를 하지 않았다. ->시간 초과

->해결 방안 : 중복을 방지하는 조합 방식을 사용했다.

조합 방식을 사용하기 위해서 1번부터 차례대로 증가하는 수에 대해서만 조합을 수행했다.

쉽게 말하면, 총 3개의 숫자를 1~10에서 선택한다고 가정하자.

그럼 1을 선택할 경우1-> 2 -> 3 이런 식으로 첫 수를 결정한다.

만약 2를 선택했을 경우 2-> 1-> 3 이런 식으로 조합할 경우 첫 경우와 완전히 겹친다.(순서가 중요하지 않음)

그렇기 때문에 2-> 3-> 4 식으로 증가하는 순으로 조합할 경우 더 작은 수를 먼저 골랐을 때와 겹치지 않는다.

 

이를 위해 linked[] 배열을 선언하여 사다리를 놓을 수 있는 모든 곳 ((N-1) * H ) 을 인덱싱하여 배열로 처리한다.

즉 사다리가 3개 있고 H가 3칸일 경우 사다리를 그릴 수 있는 곳은 총 6곳이 되는데,

세로줄 b의 번호가 1이고 높이 a 가 1일 경우 ( 1<->2 를 이어주는 a 높이 가로선) 

idx = (a-1) * (n-1) + b 가 된다.

왜냐하면 (n-1) 개가 a-1 층까지의 경우와 대응되고, b=1 ~ (n-1) 까지로 결정하기 위해서이다.

 

또한 linked[0] = 0 , linked[n*h] = 0 으로 남겨두기 위해서인데, 

이는 linked[i] 가 i 와 i+1이 연결되어 있다는 것을 의미하기 때문에 0번과 n*h는(사다리의 끝)

항상 0으로 남아있어야 하기 때문에 범위를 저렇게 정했다.

(대충 놓을 수 있는 모든 곳에 순서를 매겼다는 말이다.)

 

사다리를 모두 선택했을 경우(put함수의 num=0) 모든 사다리가 자기 자신의 번호로 가는지 확인(check함수)하고

만약 된다면 바로 모든 함수를 종료하고 놓은 사다리를 리턴한다. 

이때 놓은 사다리는 0개부터 3개로 증가하면서 놓기 때문에 바로 종료해도 가장 적게 설치하는 경우가 된다.

또한 사다리는 오른쪽으로 놓는 경우만 계산해 중복을 없앴다.

 

전체코드

#include <stdio.h>
int n, m, h;

int ladder[12][12][31];//a->b at H
int linked[10*30 + 10]; //indexing


//자기 자신의 번호로 가는지 idx=1 -> x=1 도착확인
int goDown(int idx) {
	int x = idx, y = 1;
	while (y <= h) {
		int px = x- 1, nx = x + 1;
		if (ladder[x][px][y]) {
			x = px;
		}
		else if (ladder[x][nx][y]) {
			x = nx;
		}
		y++;
	}
	if (x == idx) return 1;
	return -1;
}
//모든 번호에 대해 자기 자신으로 가는지 확인
int check() {
	for (int i = 1; i <= n; i++) {
		if (goDown(i) == -1) return 0;
	}
	return 1;

}
//사다리 놓기 num=남은 사다리 개수 idx= 인덱싱한 번호
int put(int num, int idx) {
	//모두 놓았을 경우
	if (num == 0) {
		//모두 자기 자신을 가리키면 1리턴
		if (check()) {
			return 1;
		}
		return 0;
	}

	//오른쪽으로만 연결 idx= (n-1)*(a-1) + b => (idx-b)/(n-1) +1 = a;
	for (int i= idx+1; i<=(n-1)*h; i++){
		//이미 연결된 애일 경우 
		if (linked[i]) continue;

		// 사다리 놓을 곳의 층(H)과 놓을 세로줄의위치 역산
		int a = (i / (n - 1))+1;
		int b = 0;
		//나누어 떨어지면 b=n-1
		if (i % (n - 1) == 0) {
			a--;
			b = (n - 1);
		}
		else {
			b = i - (a-1) * (n - 1);
		}
		//사다리가 이미 연결된 경우 패스
		if (ladder[b][b + 1][a] == 1) continue;
		if (ladder[b - 1][b][a] == 1) continue;
		//놓으려는 위치 오른쪽 세로줄과 연결된 애가 있어도 패스
		if (ladder[b + 1][b + 2][a] == 1) continue;
		//연결
		linked[i] = 1;
		ladder[b][b + 1][a] = 1;
		ladder[b + 1][b][a] = 1;
		//dfs
		if (put(num - 1, i)) return 1;
		//연결해제
		linked[i] = 0;
		ladder[b][b + 1][a] = 0;
		ladder[b + 1][b][a] = 0;

	}
	return 0;
}

int solve(int m) {
	//사다리 0~3개 설치해보기
	for (int i = 0; i <= 3; i++) {
		if (put(i,0)) return i;
	}
	return -1;

}

int main() {
	scanf("%d %d %d", &n, &m, &h);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		ladder[b][b + 1][a] = 1;
		ladder[b + 1][b][a] = 1;
		linked[(n-1) * (a-1) + b] = 1;
	}
	int ans = solve(m);
	printf("%d\n", ans);
}