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

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

15684번: 사다리 조작

 

풀이과정

1. 사다리를 조작해 시작과 끝점이 같도록 만드는 문제이다. 1에서 시작해서 1로 끝나면 된다.

 

2. 최대 3개의 사다리를 추가할 수 있어 시작 answer = 4로 정했다.

 

3. solution함수에 다음 시작점인 x, y를 추가하지 않아, 시간 초과가 발생했다.

 

4. map[y][x]가 1이라면 x + 1 지점과 연결되었다는 생각으로 문제를 풀었다. 

반대로 map[y][x]가 0이지만 , map[y][x-1]이 1이라면 연결되어 있다.

 

소스코드 (완전탐색, c++)

#include <stdio.h>

int map[30][10];
int N, M, H;
int answer = 4;

int lineMove(int num)
{
	int x = num, y = 0;
	while (1) {
		if (y >= H) {
			return num == x;
		}
		if (map[y][x] == 1) {
			x++;
			y++;
		}
		else {
			if (x - 1 >= 0 && map[y][x - 1] == 1) {
				x--;
				y++;
			}
			else {
				y++;
			}
		}
	}
}

bool lineCheck()
{
	for (int i = 0; i < N; i++) {
		if (!lineMove(i)) {
			return false;
		}
	}
	return true;
}

void solution(int depth, int x, int y)
{
	if (depth > 3 || answer <= depth) return;

	if (lineCheck()) {
		if (answer > depth) {
			answer = depth;
		}
		return;
	}

	for (int i = y; i < H; i++) {
		for (int j = x; j < N - 1; j++) {
			if (map[i][j] == 1) continue;
			int prevX = j - 1;
			int nextX = j + 1;
			if (prevX >= 0 && map[i][prevX] != 0) continue;
			if (nextX < N && map[i][nextX] != 0) continue;
			map[i][j] = 1;
			solution(depth+1, j+1, i);
			map[i][j] = 0;
		}
		x = 0;
	}
}

int main()
{
	scanf("%d %d %d", &N, &M, &H);
	for (int i = 0; i < M; i++) {
		int x, y;
		scanf("%d %d", &y, &x);
		map[y-1][x-1] = 1;
	}
	if (M == 0) {
		printf("0\n");
	}
	else {
		solution(0, 0 ,0);
		printf("%d\n", answer == 4 ? -1 : answer);
	}
}

 

결과