백준 15684 [C++]

www.acmicpc.net/problem/15684

15684번: 사다리 조작

1. 풀이방법

 

- 일단 사다리에 대한 표현을 어떻게 할까 고민하다가 저는 char 2차원배열을 선언해서 'R' 또는 'L' 을 넣어서

 

- 오른쪽으로 가는 경우, 왼쪽으로 가는 경우를 구현했습니다.

 

- 그렇게 선언한 후 어떤식으로 찾을 까 고민을 하다가(약간 막막)

 

- 추가하는 최대 line의 수가 3보다 많아지면 그냥 -1을 출력하라는 조건을 보고 아 dfs를 돌리는데 깊이가 3보다 커지

 

- 면 return을 하는 식으로 구현해야겠다 ( 깊이 3정도니까 전체를 다 보아도 시간초과가 안나겠지???) 라는 생각...!!

 

 

 

 

2. 주의사항

 

- 저 같은 경우 아주 초보적인 실수를 했는데 코드에도 주석으로 달아 놓겠지만.....

 

- 2차원배열로 dfs를 돌때!!

 

- for(int i=x;i<....){

        for(int j=y;j<....{

                     function (i,j+1,cnt+1);       

                  }

            }

 

-이런식으로 했다가 헤맸습니다... 이러면 안쪽반복문을 i가 갱신될때는 0부터 돌아야하는데 계속 y부터만 돌게 됩니다

 

- 저는 안쪽반복문은 그냥 계속 0부터 돌게끔 수정했습니다....(그래서인지 다른 사람들보다는 시간이 약간 길게 걸린 듯)

 

 

 

 

 

3. 나의코드

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

int N, M, H;
char sadari[31][11];
int a, b;
int minresult=4; //3 이하; 그 이상은 -1;
bool suc = false;

void inputs() {
	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		sadari[a][b] = 'R';
		sadari[a][b + 1] = 'L';
	}
}
bool checkingright() {
	for (int i = 1; i <= N; i++) {
		int resultcount = i;
		for (int j = 1; j <= H; j++){
			if (sadari[j][i] == 'R') i++;
			else if(sadari[j][i]=='L') i--;
			else continue;
		}
		if (resultcount != i) return false;
		i = resultcount;
	}
	return true;
}
void findline(int x,int cnt) {
	if (cnt > 3) { return; } 
	if (checkingright() == true) {
		if (minresult > cnt) { minresult = cnt; }
		suc = true;
		return;
	}; //성공
	for (int a = x; a < N; a++) {
		for (int b = 1; b <= H; b++) {// for(int b=y;b<=H;b++) xxxxxxxxxx!
			if (sadari[b][a] != 0 || sadari[b][a+1]!=0) continue; //이미 연결되어있음
			else {
				sadari[b][a] = 'R';
				sadari[b][a + 1] = 'L';

				findline(a,cnt + 1);  //findline(a,b+1,cnt+1) xxxxxxxx!

				sadari[b][a + 1] = 0;
				sadari[b][a] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	findline(1,0);
	if (suc == false) { cout << -1 << "\n"; }
	else cout << minresult << "\n";
	return 0;
}