글 읽기 - DLX로 풀었는데도 시간초과가 뜨네요

solo5star 3년 전 0

이 문제는 Knuth X 알고리즘으로 푸는 것이 아닌가요?

Dancing Links 및 Knuth X 알고리즘 구현하여 풀었음에도

2%에서 계속 시간초과가 뜹니다... 딱 한번 20%까지 갔는데 그래도 시간초과 뜨네요.

혹시 추가로 최적화 해야하는 부분이 있을까요?

제출 번호는 25461887입니다

solo5star 3년 전 0

통과했습니다.

백트래킹할 때 dancing links에서 for문으로 방문하면서 uncover하는 부분이 있었는데, it->right로 순회하는 것을 it->left로 바꾸니 통과했습니다. (소스코드 참고)

it->right로 했을 땐 2580번을 통과했었는데 정답 자체엔 문제가 없었던 것 같습니다.

왜 이런건지 오래 고민했는데 잘 모르겠네요... 결국 DLX로 푸는 것이 맞았습니다.

	// cover the selected column
	cover(selected);

	for (node* it = selected->down; it != selected; it = it->down) {
		int x = points[it->row].x;
		int y = points[it->row].y;
		int value = points[it->row].value;

		for (node* jt = it->right; jt != it; jt = jt->right) {
			cover(jt->column);
		}

		if (search()) {
			table[points[it->row].y][points[it->row].x] = points[it->row].value;
			return true;
		}

        // uncover 순회하는 부분. it->right 를 it->left 로 수정
		for (node* jt = it->left; jt != it; jt = jt->left) {
			uncover(jt->column);
		}
	}

	// uncover, go back and try another
	uncover(selected);

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

문제

문제

출처

ICPC

DLX로 풀었는데도 시간초과가 뜨네요

solo5star 3년 전 0

solo5star 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말