[백준] 15684번: 사다리 조작

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

15684번: 사다리 조작

문제 이해

사다리에 가로선들을 추가해보는 모든 경우를 탐색한다.

하지만 사다리는 최대 3개만 놓을 수 있어서, 3개를 넘게 놓는 경우는 패스해준다.

0개, 1개, 2개, 3개 놓는 경우 중 조건에 해당하는 경우가 되면 그 때의 추가한 사다리 개수에 따라 min값을 갱신해주면 되는 문제이다.

 

map[i][j]는 j번 사다리에 j+1번으로 가는 (= 오른쪽으로 가는) 높이 i에 있는 사다리가 있다는 뜻이다.

그렇다는 건 j+1번 사다리에는 j번으로 가는 (=왼쪽으로 가는) 높이 i에 있는 사다리가 있다는 뜻이다. 

 

Check()

이 규칙을 이용해서 a번 사다리에서 a번 사다리로 가는지를 확인하는 것은 쉽다.

일단 처음에 현재위치 (cur)을 a로 잡아둔다.

위에서부터 내려가면서 cur 위치를 바꿔주면 된다.

map[a][h] 가 1이면 cur += 1 해주고, map[a-1][h] == 1이면 cur -= 1해주면 된다.

끝까지 내려왔을 때 cur == a이면 원래 위치로 돌아온 거니까 continue, 아니면 이 경우는 불가능한 경우이므로 return 0해주면 된다. 

int Check(void) {
	// 현재 맵의 상태에서 모든 시작점 == 도착점인지
	for (int i = 1; i <= N; i++) {
		int cur = i;
		for (int j = 1; j <= H; j++) {
			if (map[j][cur] != 0) cur += 1;
			else if (map[j][cur - 1] != 0) cur -= 1;
		}
		if (cur != i) return 0;
	}
	return 1;
}

 

DFS()

<재귀 부분>

DFS가 조금 헷갈리는데 모든 사다리들에 한 번씩 추가해보는 작업을 해야해서 이중 for문을 이용한다.

현재 위치에 사다리가 있는 거면 그냥 넘어가고, 

없는 상태면 한번 넣어보고 다음 DFS를 했다가, 돌아와서 다시 사다리를 없애준다.

 

<조건 확인 부분>

0개, 1개, 2개, 3개를 추가한 상태에서 모두 지금 사다리 상태가 조건에 부합하는지 (i번 사다리의 도착점은 i번) 를 확인해야 하므로, 항상 Check()를 해준다.

 

<종료 부분>

만약 3개 이상 추가한 경우라던가, 지금까지의 min_added값보다 많이 추가한 경우는 return해서 가지치기 해준다.

void DFS(int idx, int added) {

	// 종료
	if (added > 3 || added > min_added) {
		return;
	}

	if (Check()) {// 현재 맵의 상태에서 사다리 성공인지
		if (added < min_added) min_added = added;
		return;
	}

	for (int i = idx; i <= H; i++) {
		for (int j = 1; j < N; j++) {
			if (map[i][j] != 0) continue;
			if (map[i][j - 1] != 0) continue;
			if (map[i][j + 1] != 0) continue;

			map[i][j] = M + 1 + added;
			DFS(i, added + 1);
			map[i][j] = 0;
		}
	}
}

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 10
#define MAXM 9*30
#define MAXH 30

int N, M, H; // 세로선, 기존 가로선 개수, 가로선
int map[MAXH + 5][MAXN + 5];
int min_added = 0x7fffffff;

void Get_Input(void) {
	int a, b;
	scanf("%d %d %d", &N, &M, &H);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d", &a, &b);
		map[a][b] = i; // b, b+1 번 사이에 a번째 가로선이 있다
	}
}

int Check(void) {
	// 현재 맵의 상태에서 모든 시작점 == 도착점인지
	for (int i = 1; i <= N; i++) {
		int cur = i;
		for (int j = 1; j <= H; j++) {
			if (map[j][cur] != 0) cur += 1;
			else if (map[j][cur - 1] != 0) cur -= 1;
		}
		if (cur != i) return 0;
	}
	return 1;
}

void DFS(int idx, int added) {

	// 종료
	if (added > 3 || added > min_added) {
		return;
	}

	if (Check()) {// 현재 맵의 상태에서 사다리 성공인지
		if (added < min_added) min_added = added;
		return;
	}

	for (int i = idx; i <= H; i++) {
		for (int j = 1; j < N; j++) {
			if (map[i][j] != 0) continue;
			if (map[i][j - 1] != 0) continue;
			if (map[i][j + 1] != 0) continue;

			map[i][j] = M + 1 + added;
			DFS(i, added + 1);
			map[i][j] = 0;
		}
	}
}


int main(void) {
	Get_Input();
	if (M == 0) {
		printf("0");
		return 0;
	}
	DFS(1, 0);
	if (min_added == 0x7fffffff) printf("-1");
	else printf("%d", min_added);
	return 0;
}