백준 15684 - 사다리 조작

문제링크

• 백준 15684

문제설명

• 사다리 게임으로 N개의 세로선, M개의 가로선을 놓을 수 있다.
• H는 가로선을 놓을 수 있는 위치를 보여주며 모든 세로선을 가로지르는 점선의 개수이다.
• 세로선의 개수, 가로선의 개수, 그리고 H가 주어진 사다리 상황에서 최대 3개의 가로선을 추가할 수 있는데, i번 세로선에서 출발해서 i번에 도착하도록 만들기 위한 추가해야 하는 가로선의 최솟값을 찾아라.
• 정답이 3보다 크거나, 불가능한 경우 -1을 출력하라.

입력

• 세로선 개수(N), 가로선 개수(M), 세로선마다 가로선을 놓을 수 있는 위치 개수(H)가 주어짐
• M개의 줄에 걸쳐 가로선의 정보가 한 줄에 하나씩 주어진다. (a, b)
  • b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미

문제접근

• Dfs를 적용하는 방법을 고민할 때, 시간 복잡도를 고려하다보니 이중반복문의 Dfs를 활용하겠다는 생각은 가장 마지막 순서였다.
• 문제의 시간제한은 2초로 주어졌고, 최대 3개까지만 놓을 수 있으니 이중반복문의 Dfs를 적용하여 문제를 풀 수 있다는 생각이 들었다.
• 기저사례는 이미 답을 구한 경우이거나 추가 가로선을 모두 놓은 경우이다.
• ladder[row][col]=1 은 row번 점선 위치에서 세로선 col, col+1번이 연결되었음을 의미한다.
• 추가 가로선은 ladder[row][col]을 기준으로 좌측, 우측에 위치한 사다리에 가로선이 없을 때만 놓을 수 있다.
• 사다리 타기를 함수로 구현할 때는 ladder[row][col]=1 인 경우 col+1로 이동해야하고, ladder[row][col-1]=1 인 경우 col-1로 이동해야한다.

구현 1(All Pass)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool CheckLadder(vector<vector<int>>& ladder) {
	int h = ladder.size(); // 가로 점선
	int n = ladder[0].size(); // 세로선

	for (int c = 1; c < n-1; c++) { // 1 ~ n-1
		int ccol = c;
		for (int r = 1; r < h; r++) { // 1 ~ h
			int left = ccol - 1;
			if (ladder[r][left] == 1) ccol = left;
			else if (ladder[r][ccol] == 1) ccol++;
		}
		if (ccol != c) return false;
	}
	return true;
}

void Dfs(vector<vector<int>>& ladder, int cnt, int m, bool& flag) {
	// 기저사례: 이미 답을 구한 경우
	if (flag) return;

	// 기저사례: cnt==m, 추가 사다리를 모두 놓은 경우
	if (cnt == m) {
		if (CheckLadder(ladder)) {
			flag = true;
			return;
		}
		return;
	}
	
	int h = ladder.size(); // h+1
	int n = ladder[0].size();
	for (int c = 1; c < n-1; c++) { // 1 ~ n-1
		for (int r = 1; r < h; r++) { // 1~h
			int left = c - 1;
			int right = c + 1;
			if (ladder[r][left] || ladder[r][right] || ladder[r][c]) continue;
			ladder[r][c] = 1;
			Dfs(ladder, cnt + 1, m, flag);
			ladder[r][c] = 0;
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int N, M, H, a, b;
	cin >> N >> M >> H;

	// b번 세로선과, b+1번 세로선을 a번 점선 위치에서 연결
	// ladder[a][b] = 1
	vector<vector<int>> ladder(H + 1, vector<int>(N+1, 0));
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		ladder[a][b] = 1;
	}

	bool flag = false;
	int ans = -1;
	for (int m = 0; m < 4; m++) {
		Dfs(ladder, 0, m, flag);
		if (flag) {
			ans = m;
			break;
		}
	}
	cout << ans << endl;
	return 0;

}

• 처리시간을 줄이기 위해 답을 찾은 경우 빠르게 함수를 빠져나오도록 flag 장치를 두었다.