백준 15684번 사다리 조작 (C++)

문제

정답 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
int N,H;//점선 가로, 점선 세로
int M;//놓인 가로
bool table[31][11]; // table[H][N-1]

int ret =  5;
int dp[31][11];
bool calcDp(){//초기 주어진 값으로 dp배열 계산
	for(int i=1;i<=N;i++)
		dp[0][i]=i;
	for(int i=1; i<=H; i++){
		for(int j=1;j<=N;j++){
			if (table[i][j]){//줄이 있는 경우 둘의 위치 교환
				int tmp = dp[i-1][j];
				dp[i][j] = dp[i-1][j+1];
				dp[i][j+1] = tmp;
				j++;
			}
			else 
				dp[i][j] = dp[i-1][j];
		}
	}
	for(int i=1;i<=N;i++){
		if (dp[H][i] != i)
			return false;
	}
 	return true;
}

void dfs(int high ,int cnt){
	if (cnt > 3)
		return ;
	if (calcDp() == true)
	{
		ret = min(ret, cnt);
		return ;
	}
	for(int i=high;i<=H;i++){
		for(int j=1;j<N;j++){
			if (table[i][j] || table[i][j-1] || table[i][j+1]) continue;
			table[i][j] = true;
			dfs(i,cnt+1);
			table[i][j] = false;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> N >> M >> H;
	for(int i=0;i<M;i++){
		int a,b;
		cin >> a>>b;
		table[a][b] = true;
	}
	dfs(1,0);
	if (ret == 5)
		ret = -1;
	cout << ret << "\\n";

}

문제 풀이의 흐름

이 문제는 처음에 설마 시간 계산을 잘못해서 틀렸던 문제입니다.

실패 코드

/*

- 추가해야하는 가로선의 최소갯수
- i번 세로선의 결과가 i가 나와야 한다.
	놓는 가로선을 
	
	1     2     3     4    5 ->N 
1
  (1,1) (1,2) (1,3) (1,4) (a,b)
2

3

4

5

6

|
H

풀이 생각 
모든 놓을 수 있는 자리에 다리를 놓는 방식 
최대 30개 * 10 300칸 300 C 3
300개 중 순서에 상관없이 3개를 뽑으면 되므로 300*299*298 /3*2 대충 100*100*100*5 => 5,000,000 (5백만)

사다리를 타는 연산 시간 : 사다리당 높이만큼 연산 -> 전부 계산하는데 300번 연산 진행
만약 브루스 포스로 하게 되면  15억정도 진행됨 (15초..)

바뀌는 줄 이전의 결과 즉 그곳을 지나지 않는 경로를 가진 녀석들의 결과는 변경되지 않는다.
dp배열처럼 사용할 수 있지 않을까?
가로선은 서로 접하면 안된다.
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
int N,H;//점선 가로, 점선 세로
int M;//놓인 가로
bool table[31][11]; // table[H][N-1]

int dp[31][11];//몇번줄 상태일 때 -> 어떤 유저가 있는지
int dp2[31][11][31][11];//숫자를 추가했더니 몇번 줄 상태일 때 -> 어떤 유저가 있는지
int dp3[31][11][31][11][31][11];//숫자를 2개 추가했더니 몇번 줄 상태일 때 -> 어떤 유저가 있는지

int ret = -1;

bool calcDp(){//초기 주어진 값으로 dp배열 계산
	cout << "--------------첫 디피 결과!-----------------\\n";
	for(int i=1;i<=N;i++)
		dp[0][i]=i;
	for(int i=1; i<=H; i++){
		for(int j=1;j<=N;j++){
			if (table[i][j]){//줄이 있는 경우 둘의 위치 교환
				int tmp = dp[i-1][j];
				dp[i][j] = dp[i-1][j+1];
				dp[i][j+1] = tmp;
				j++;
			}
			else 
				dp[i][j] = dp[i-1][j];
		}
	}
	for(int i=1;i<=H;i++){
		for(int j=1;j<=N;j++) cout <<dp[i][j] << "|";
		cout << "\\n";
	}
	for(int i=1;i<=N;i++){
		if (dp[H][i] != i)
			return false;
	}
	ret = 0;
 	return true;
}

void print_table(){
	cout << "---------------테이블 출력---------------\\n";
	for(int i=1;i<=H;i++){
		for(int j=1;j<=N;j++)
			cout << table[i][j] << "|";
		cout << "\\n";
	}
}

bool calcOneStart(int line,int x){
	for(int i=line;i<=H;i++){
		for(int j =1;j <=N;j++){
			
		}
	}
}

bool addOneLine(){
	for(int i=H;i>0;i--){
		for(int j=N-1;j>0;j--){
			if (table[i][j-1] == true || table[i][j+1] == true)
				continue;
			table[i][j] = true;
			if (calcOneStart(i))
				return true;
			table[i][j] = false;
		}
	}
	return false;
}

bool addTwoLine(){
	for(int i=H;i>0;i--){
		for(int j=N-1;j>0;j--){
			for(int k=H;k>0;k--){
				for(int l=N-1;l>0;l--){
					
				}
			}
		}
	}
	return false;
}

bool addThreeLine(){
	for(int i=H;i>0;i--){
		for(int j=N-1;j>0;j--){
			for(int k=H;k>0;k--){
				for(int l=N-1;l>0;l--){
					for(int y=H;y>0;y--){
						for(int x=N-1;x>0;x--){
							
						}
					}
				}
			}
		}
	}
	return false;
}

int main(){
	cin >> N >> M >> H;
	for(int i=0;i<M;i++){
		int a,b;
		cin >> a>>b;
		table[a][b] = true;
	}
	print_table();
	if ( calcDp()|| addOneLine() || addTwoLine() || addThreeLine()) ;
	cout << ret << "\\n";

}

처음 시도는 이 문제는 dp를 이용해서 풀면 되겠다고 생각했습니다.

아무것도 추가하지 않고 값을 계산하고 하나를 추가하는 방식으로 진행하면 될 것 같았습니다.

그것의 핵심 아이디어는 아래쪽에 사다리를 하나 추가하면 그 위쪽은 이전의 결과값을 그대로 사용하면 된다는 아이디어를 얻었기 때문입니다.

그래서 아무것도 추가하지 않은 결과에서 아래쪽에서 올라가면서 문제를 해결하면 dp배열을 이용해서 풀 수 있을 것 같다고 생각했습니다.

그러나, 코드의 구현이 너무 어렵고, 6중 포문이 나오는 방식을 보고 차라리 브루스포스로 푸는건 어떨까하고 방향을 바꿨습니다.

dfs로 재귀적으로 하나씩 증가하고 모든 것을 다 돌게 하면 작은 수에서 효율이 안 나오는데, 저는 최악의 상황에 효율이 아니라 일반적인 효율을 생각해서 틀렸던 문제입니다.

위쪽 코드의 경우 dfs는 코드를 보면서 쉽게 이해가 가능할 것 같습니다.

주의 할 점

은근히 좌표체계가 헷갈리는 문제입니다.

입력을 잘못받지 않도록 주의하세요.

저는 X와 Y를 그래프와 같게 처리하는 풀이가 편해서 보통 그렇게 바꿔서 풀고 있습니다.

반성 및 고찰

앞으로는 dp를 하기 전에 브루스포스로 했을 때 시간초과가 나는지 잘 계산하고 진행해야겠다고 다짐했습니다!