[Algorithm][C++] BOJ 15684 사다리 조작

url: https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

풀이 핵심

1. Bruth Force && Back Tracking 알고리즘 문제로 보인다. (추가한 사다리 수가 3보다 크다면 더 이상 탐색할 필요 없으므로 모두 탐색 할 수 있다)

 

2. DFS 이용

- check(DFS) 함수 탈출 조건

• 현재 사용한 사다리 수가 ans 보다 크거나 같다면 return
• 현재 사다리의 각 번호들이 맨 밑까지 내려왔을 때 동일 한지 확인 (맞다면 정답에 저장 후 return)
• 현재 사용한 사다리 수가 3이라면 다음 사다리 사용 수 는 4이므로 return

if (cnt >= ans) return;
if (isRight()) {
  ans = cnt;
  return;
}
if (cnt == 3) return;

 

3. 탐색 횟 수를 줄이기 위해 현재까지 탐색한 사다리 열, 행을 chekc(DFS) 함수 인자로 전달

void check(int cnt, int r, int c);

 

4. isRight 함수로 현재 사다리의 각 번호들이 맨 밑까지 내려왔을 때 동일 한지 확인

• 사다리 저장 방식은 다음과 같이 한다.

// 입력 받을 때
int a, b;
scanf("%d %d", &a, &b);
ladder[a][b] = b + 1;
ladder[a][b + 1] = b;

 

• isRight 함수

for (int i = 1; i <= N; i++) {
  int c = i;
  int r = 1;
  while (1) {
      if (r == H + 1) {
        if (c != i) return 0;
        break;
      }
      if (ladder[r][c]) {
        c = ladder[r][c];
      }
      r++;
  }
}

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N, M, H;
int ladder[30 + 1][10 + 1];
int ans = 4;

int isRight() {
	for (int i = 1; i <= N; i++) {
		int c = i;
		int r = 1;
		while (1) {
			if (r == H + 1) {
				if (c != i) return 0;
				break;
			}
			if (ladder[r][c]) {
				c = ladder[r][c];
			}
			r++;
		}
	}
	return 1;
}

void check(int cnt, int r, int c) {
	if (cnt >= ans) return;
	if (isRight()) {
		ans = cnt;
		return;
	}
	if (cnt == 3) return;

	for (int i = r; i <= H; i++) {
		for (int j = c; j <= N - 1; j++) {
			if (ladder[i][j] || ladder[i][j + 1]) continue;
			ladder[i][j] = j + 1;
			ladder[i][j + 1] = j;
			check(cnt + 1, i, j);
			ladder[i][j] = ladder[i][j + 1] = 0;
		}
		c = 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[a][b] = b + 1;
		ladder[a][b + 1] = b;
	}
	check(0, 1, 1);
	if (ans == 4) ans = -1;
	printf("%d", ans);
	return 0;
}