[C++] 백준 15684 사다리 조작

문제 링크

---

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

15684번: 사다리 조작

 

접근 방법

---

 이 문제는 사다리에 추가적으로 가로선을 0개 부터 최대 3개까지 놓는 가능한 모든 경우의 수를 다 보아야 해결 할 수 있다.  결국 조합 문제로 해석될 수 있으므로, 백트래킹을 하며 모든 조합에 대해 문제의 조건은 1번째부터 i번째에서 출발할 때 순서대로 1번째부터 i번째의 도착 지점에 도달하면 카운트하고, 그 카운트가 4이상이거나 가능한 방법이 없다면 -1을 출력하면 된다.

 

(1) 변수

map[h][l]는 h의 높이, l번째 라인이 h의 높이, l+1번째 라인에 가로선이 연결되어 있다면 1, 아니면 0으로 나타낸다.  

 

(2) go() 함수

bool go() {
	for (int i = 1; i <= N; i++) {
		int nowl = i; 
		for (int nowh = 0; nowh <= H; nowh++){
			if (map[nowh][nowl] == 1) 
				nowl++;
			else if (map[nowh][nowl - 1] == 1) 
				nowl--;
		}
		if (nowl != i)
			return false;
	}
	return true;
}

이 함수는 사다리의 출발지점과 도착지점이 같은지 따라가보는 함수이다.

 모든 사다리의 출발지점 1~N에 대해 확인 하여야 하기 때문에 for문에서 경우를 검사해보자. 현재 출발 라인을 nowl = i 라 하고, nowh(0~H)를 따라갈때, 우측에 사다리가 있는 경우 (if(map[nowh][nowl] == 1))   라인을 오른쪽으로 옮겨갈 것(nowl++)이고, 좌측에 사다리가 있는 경우 (if(map[nowh][nowl - 1] == 1))   라인을 왼쪽으로 옮겨갈 것(nowl--)이다.

 

(3) solve()함수

void solve(int cnt, int now_h, int now_l) {
	if (go()) {
		result = min(cnt, result);
		return;
	}
	if (cnt == 3) 
		return;

	for (int h = now_h; h <= H; h++) {
		for (int l = now_l; l < N; l++) {
			if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0) {
				map[h][l] = 1;
				solve(cnt + 1, h, l);
				map[h][l] = 0;
			}
		}
		now_l = 1;
	}
}

이 함수는 조합을 보기 위한 백트래킹(DFS) 함수이다. 중복되는 경우를 보지 않기 위해 매게변수로(nowl, nowh)를 사용하였으며, 위 함수가 호출되는 모든 경우에 대해 위에 설명한 go()함수로 조건을 만족하는지 검사한다. cnt가 3보다 커지는 경우는 고려하지 않으므로 cnt는 3에서 return을 하게 된다.

 

 가로선을 추가 할 수 있는 경우인,

양쪽에 가로라인이 존재하지 않을 때(if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0))

가로라인을 추가(map[h][l] = 1)하고, 함수를 진행 시킨뒤(solve(cnt + 1, h, 1)), 함수가 종료되면 해당 가로라인을 다시 삭제 (map[h][l] = 0)하면 된다. 

 

소스 코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, H;
int map[32][12]; //height, line
int result = 4;	

bool go() {
	
	for (int i = 1; i <= N; i++) {
		int nowl = i; 
		for (int nowh = 0; nowh <= H; nowh++){
			if (map[nowh][nowl] == 1) 
				nowl++;
			else if (map[nowh][nowl - 1] == 1) 
				nowl--;
		}
		if (nowl != i)
			return false;
	}
	return true;
}

void solve(int cnt, int now_h, int now_l) {
	if (go()) {
		result = min(cnt, result);
		return;
	}
	if (cnt == 3) 
		return;

	for (int h = now_h; h <= H; h++) {
		for (int l = now_l; l < N; l++) {
			if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0) {
				map[h][l] = 1;
				solve(cnt + 1, h, l);
				map[h][l] = 0;
			}
		}
		now_l = 1;
	}
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> H;
	for (int i = 1; i <= M; i++) {
		int a, b;
		cin >> a >> b; //a높이 b라인
		map[a][b] = 1;
	}
	solve(0, 1, 1);
	
	if (result >= 4)
		cout << -1 << "\n";
	else
		cout << result << "\n";
}

개발 환경 : VS 2019

질문, 지적 환영입니다.