글 읽기 - 이 코드가 어떻게 정답이 될 수 있나요?

starriest30 4년 전 0

코드의 35번 라인부터 사다리를 놓을 수 있는 위치를 파악하는 코드입니다.

처음 2중 반복문을 돌릴 때 i와 j의 시작을 1로 했더니 시간초과가 나길래

바로 이전의 탐색 위치를 pi와 pj라는 인자로 각각 받아온 다음 해당 위치부터 탐색할 수 있도록 설정해 주었습니다.

그런데 지금 코드에 따르면 i번째 세로선의 j번째 위치에 가로선을 놓은 다음부터는

모든 세로선에서 j번째 가로선부터 탐색될텐데

그렇게 되면 i+1번째 세로선부터는 j-1 이하의 가로선은 탐색할 수 없는 상황이 되지 않나요?

예를 들면 2번째 세로선의 6번째 가로선에 사다리를 두면 pi와 pj에 각각 2, 6이 전달되므로 다음 dfs 는 1번째 세로선의 6번째 가로선부터 탐색을 시작하고,

2번째, 3번째.. 세로선 역시도 6번째 가로선부터 탐색을 시작하게 되지 않나요?

이 코드를 제출했을 때 정답이 떴는데, 어떻게 정답이 될 수 있는지 궁금합니다 ㅠㅠ

#include<iostream>

using namespace std;
int map[40][20]; // 세로, 가로 순서
int N, M, H;


bool run() {
	bool possible = true;
	int cur;
	for (int i = 1; i <= N; i++) {
		cur = i;
		for (int j = 1; j <= H; j++) {
			if (map[j][cur]) {
				cur += 1;
			}
			else if (cur > 1 && map[j][cur-1]) {
				cur -= 1;
			}
		}
		if (cur != i) possible = false;
		if (!possible) break;
	}

	return possible;
}

bool select(int idx, int max_val, int pi, int pj) {
	if (idx == max_val) {
		return run();
	}

	bool possible = false;

	for (int i = 1; i < N; i++) {
		for (int j = pj; j <= H; j++) {
			if (map[j][i] == 1||map[j][i-1]==1||map[j][i+1] == 1) {
				// 이미 사다리가 놓여져 있는 경우
				continue;
			}
			else {
				map[j][i] = 1;
				possible = select(idx + 1, max_val, i, j));
				map[j][i] = 0;
			}
			if (possible) break;
		}
		if (possible) break;
	}
	return possible;

}

int main(int argc, char** argv)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> H;

	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		map[a][b] = 1;
	}

	if (M == 0) cout << "0";
	else	if (run()) cout << "0";
	else {
		bool result = false;
		int i;

		// 1개 ~ 3개까지 사다리 놓아보고
		// 답이 안나오는 경우 -1
		for (i = 1; i <= 3; i++) {
			result = select(0, i, 1, 1);
			if (result) break;
		}

		if (result) cout << i;
		else cout << "-1";
	}

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.