C++ 사다리 조작

www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

I번 선수의 경로를 설정하는 것과 사다리를 선택하는 것과 헷갈려서 좀 시간이 걸린 문제 ㅜㅜ 

코드 자체는 진짜 몇 줄 필요하지 않다.

1시간 20분정도 걸려서 다 풀고 신나는 마음으로 제출했는데,,, 틀렸다!!ㅜㅜ

 

아무리 봐도 완벽한데; 의심가는 부분은 DFS 부분

항상 1차원  VISITED 배열을 만들어서 DFS로 조합을 선택하는 건 잘하는데, 2차원으로 가면 응용이 안된다. 

원래 내 코드는 DFS로 사다리를 추가하는 부분코드를 이렇게

1) 열이 마지막이면 행을 추가하고, 열을 1로 만들어주고 

2) 이외에는 행은 그대로, 열을 1추가하는 방식으로 코드를 짰다.

void dfs(int start_i, int start_j ,  int cnt, int max_cnt) {
		/*  사다리 선택	& 추가	*/
	if (max_cnt == cnt) {
		if (move()) min_ladder = min(min_ladder, max_cnt);
		return;
	}

	for (int i = start_i; i < H+1 ; i++) {
		for (int j = start_j; j < N; j++) {
			if (map[i][j] == 1 || map[i][j-1] == 1 || map[i][j+1] == 1) continue;
			map[i][j] = 1;
			if (j == N-1) dfs(i+1, 1, cnt + 1, max_cnt);
			else dfs(i, j+1, cnt + 1, max_cnt);
			map[i][j] = 0;
		}
	}
}

 

얍문님 블로그를 참고했을 때, 이런 식으로,,, 행만 인자로 넘겨줘서 한다. 

void dfs(int start_i ,  int cnt, int max_cnt) {
		/*  사다리 선택	& 추가	*/
	if (max_cnt == cnt) {
		if (move()) min_ladder = min(min_ladder, max_cnt);
		return;
	}

	for (int i = start_i; i < H+1 ; i++) {
		for (int j = 1; j < N; j++) {
			if (map[i][j] == 1 || map[i][j-1] == 1 || map[i][j+1] == 1) continue;
			map[i][j] = 1;
			dfs(i, cnt + 1, max_cnt);
			map[i][j] = 0;
		}
	}
}