[BaekJoon 15684] 사다리 조작

안녕하세요. 이번 포스팅에서는 백준 15684번 사다리 조작이라는 문제에 대해 포스팅을 해보겠습니다.

 

해당 문제는

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

15684번: 사다리 조작

 

이 링크에서 참고하실 수 있습니다. (문제가 너무 길어요 ㅜㅜ)

 

그렇다면 문제를 읽으셨다고 가정하고, 이 문제를 조금 단계별로 구조화해보겠습니다.

 

1. 사다리를 배열에 적절히 매핑하기

2. 경우의 수 구하기

3. 모든 경우의 수에 대하여 탐색

 

 

1. 사다리를 배열에 적절히 매핑하기

사실 저는 머리가 안 좋아서... 만약에 첫 번째 가로선에 2번 세로선과 3번 세로선이 사다리로 연결되어 있다면, 

 

board[1][2] = 1, board[1][3] = 1 이런 식으로 두 군데 마킹하려고 했습니다만, 실제로 그럴 필요가 없습니다.

 

무조건적으로 왼쪽에만 마킹을 하게 되면, 당연하게 다음 세로선에 연결되어 있다고 생각할 수 있습니다.

 

즉 첫 번째 가로선에 2번 세로선과 3번 세로선이 사다리로 연결되어 있다면, 

board[1][2] = 1

만 마킹해주시면 됩니다.

 

	for(int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		board[a][b]=1;
	}

 

위 코드와 같이 입력을 받을 때 가로선 기준으로 b세로선과 b+1 세로선이 연결되어 있다면 board[a][b]=1로 초기화해주었습니다.

 

2. 경우의 수 구하기

경우의 수는 두 가지 방법이 있습니다.

 

1. 전체 배열을 돌며 사다리를 추가로 생성할 수 있는 것들을 한 집합으로 모아놓고, 조합을 모두 구하여 경우의 수를 구하기.

 

2. dfs로 백트래킹 방법으로 경우의 수를 구하기.

 

두 방법 모두 알면 좋습니다. 하지만 위 문제의 경우 dfs로 구현할 경우 깊이가 3까지밖에 가지 않기 때문에 dfs로 간편하게 구현해보도록 하겠습니다.

 

3. 모든 경우의 수에 대하여 탐색

현재 탐색하는 단계에서는 말 그대로 각 세로선에서 말을 출발하여 도착하는지 보면 됩니다. 따라서 각 세로선마다 두 번째 포문을 세로선을 탐색하였고, 만약에 사다리가 다음 세로선과 연결되어있다면 cur++, 이전 세로선과 연결되어 있다면 cur--, 그리고 루프가 종료되었을 때 시작한 세로선과 끝나는 지점이 다르면 실패하였단 의미이므로 false를 return 해 주었습니다.

 

<소스 코드>

#include <bits/stdc++.h>

using namespace std;

int n, m, h, res=999999;
int board[30+5][10+5];
bool done(){
	for(int i = 1; i <= n; i++) {
		// 모든 세로선에 대하여 check
		int cur = i;
		for(int j = 0; j <= h; j++) {
			if(board[j][cur]==1) cur++;
			else if(board[j][cur-1]==1) cur--;
		} 
		if(cur != i) return false;
	}
	return true;
} 
void dfs(pair<int,int> cur, int cnt) {
	if(cnt >= res) return;
	
	if(done()) {
		res = min(res, cnt);
		return;	
	}
	if(cnt==3) return;
	
	for(int i = cur.first; i <= h; i++) {
		for(int j = cur.second; j < n; j++) {
			if(board[i][j-1]==0 && board[i][j]==0 && board[i][j+1]==0) {
				board[i][j]=1;
				dfs({i, j}, cnt+1);
				board[i][j]=0;
			}
		}
		cur.second=1;
		// **** 다음 i에서는 j가 1부터 시작하면서 check 해야함 
	} 
	return;
}

int main(void) {
	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;
		board[a][b]=1;
	}
	
	dfs({1,1}, 0);
	if(res==999999) cout << -1 << endl;
	else cout << res << endl;
		
	return 0;
}

 

 * 주의할 점

dfs를 보시면 당연히 인자로 전달받는 cur라는 변수에는 cur까지의 원소는 고려하지 말라는 뜻이므로 cur 다음부터 탐색을 하면 됩니다. 하지만 한번 모든 세로선에 대한 탐색이 끝난 뒤, 가로선을 추가하실 때는 1부터 추가하셔야 모든 경우의 수를 탐색하실 수 있습니다.

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.