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

서론

브루트포스 문제. 재귀를 이용하여 완전탐색했다.

풀이

의사코드는

main(){
    사다리 입력받음
    사다리설치()
    결과 출력
}


사다리설치(좌표, 추가한 사다리 개수, 사다리 설치){
	
    if(좌표가 지도의 끝){
    	사다리를 탄다();
        if(사다리를 타보니 조건이 맞다) 결과 갱신
    }
    다음칸으로 이동할 좌표 생성
    
    if(다음칸 사다리가 설치되어 있지 않다){
    	다음칸 사다리 설치
        사다리설치(다음칸 좌표, 추가한 사다리 개수+1, true)
        다음칸 사다리 회수
    }
    사다리설치(다음칸 좌표, 추가한 사다리 개수, false)
}

먼저 사다리를 지도에 입력해야하는데, 입력조건에 보면 가로선의 정보는 a, b로 나타내고 b번 세로선과 b+1번 세로선을 a 점선위치에 연결했다는 내용이 나온다. 이를 착안하여 사다리를 입력할 2차원배열을 만들고, 배열의 각 칸을 문제 그림의 가로선과 세로선이 만나는 점으로 한다. 그리고 사다리는 현재 칸이 1이면 현재 칸의 x와 x+1의 사이의 사다리를 나타낸다.

사다리를 설치하는 방법은 재귀를 이용한다.

https://hydroponicglass.tistory.com/30

위 링크의 문제와 같은 방식으로 재귀를 이용하여 2차원 배열의 칸들에 사다리를 1~3개까지 추가적으로 설치하는 모든 경우의 수를 탐색한다. 그리고 각각의 경우의 수에 대해 사다리를 태워서 조건에 맞는지 확인한다. 조건에 부합하면 결과값을 갱신한다.

사다리를 태우는 방법은

왼쪽 첫 열에서

y가 1에서 h에 도착할때까지 y값을 1 증가시키고 사다리가 현재칸에 있으면 x를 +1, 왼쪽칸에 있으면 x를 -1 하는것을 반복한다. 그리고 h에 도착했을때 x값이 현재 열의 값과 같으면 다음열로 넘어가서 위와 같은 방식으로 확인해주고 마지막열까지 확인되었다면 결과값을 갱신한다.

구현

// c++

#include <iostream>
#include <algorithm>

int map[31][11];
int result = -1;
int n, m, h;

bool cal() {
	bool continueFlag = true;
	for (int i = 1; i <= n; i++) {
		int x = i;
		int y = 1;
		while (y <= h) {
			if (x < n && map[y][x] == 1) x++;
			else if (x > 1 && map[y][x - 1] == 1) x--;
			y++;
		}
		if (x != i) { 
			continueFlag = false;
			break;
		}
	}
	return continueFlag;
}

void addLadder(int y, int x, int ladderCnt, bool set) {
	if (ladderCnt > 3) return;

	if (y >= h && x >= n) {
		bool tf = cal();
		if (tf == true) {
			if (result == -1) result = ladderCnt;
			else result = std::min(result, ladderCnt);
		}
		return;
	}
	else if (x == n) {
		y++;
		x = 1;
	}
	else {
		x++;
	}

	if (x < n && map[y][x] == 0  && map[y][x + 1] == 0) {
		map[y][x] = 1;
		addLadder(y, x, ladderCnt + 1, true);
		map[y][x] = 0;
	}
	addLadder(y, x, ladderCnt, false);

	return;
}

int main() {
	std::cin >> n >> m >> h;
	for (int i = 0; i < m; i++) {
		int a, b; // a는 가로선, b는 세로선
		std::cin >> a >> b;
		map[a][b] = 1; // 1이면 b와 b+1사이에 사다리 존재, -1이면 b와 b-1 사이에 사다리 존재
	}

	addLadder(1, 0, 0, false);

	std::cout << result;
}