글 읽기 - 백트레킹 함수로 가능한 중복 없이 모든 조합을 만들었는데, 시간 초과가 납니다.

gun0317 5년 전 0

백트레킹으로 모든 점에서 시작점을 기준으로, 한번 방문했던 시작점은 0으로 돌리는 것이아닌 다른 임의의 숫자(3)으로 만들어서 해당 부분에 중복 접근하지 못하게 하였습니다.

그 후 상하좌우 순으로 인접한 블록이 있는지 여부를 검사하는 validity 함수를 사용하여 가능한 테트로미노의 모든 조합을 구하였습니다.

구한 조합으로 마스킹을 하여 ans를 업데이트하는 calculate 함수를 사용하였습니다.

디버깅을 하면서 보니 정사각형 모양이 중복으로 발생하긴 하지만 2~3회만 만드는 것으로 보여 중복 제거가 문제인지는 잘 모르겠습니다.

채점 0%에서 시간초과가 납니다. 예제와 https://www.acmicpc.net/board/view/32956 에 jaeyoon8783님이 올려주신 케이스 및 질문 게시판 몇 개 반례는 모두 통과가 됩니다. 아무래도 크기가 큰 경우에 시간초과가 나는 듯 한데 어떻게 해결해야할 지 모르겠습니다 ㅠ

디버깅 시 아래와 같이 1이 4개가 조합되면 calculate함수를 실행합니다.

이미 지나온 시작점은 3으로 표시하여 1이 표시되지 않게 하였습니다.

다음 번 조합입니다.

읽어주셔서 감사합니다.

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
int map[510][510], visited[510][510];
int N, M, ans;
void back(int depth, int curR, int curC);
void calculate();
bool validity(int r, int c, int visited[510][510]);
int dr[] = { -1,1,0,0 }, dc[] = { 0,0,-1,1 };

int main() {
	cin >> N >> M;
	for (int r = 0; r < N; r++)
		for (int c = 0; c < M; c++)
			scanf(" %d", &map[r][c]);

	back(0, 0, 0);
	cout << ans << endl;
	return 0;
}

void calculate() {
	int sum = 0;
	int flag = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (visited[r][c] == 1) {
				sum += map[r][c];
				flag++;
			}
			if (flag == 4) break;	// 시간 단축을 위해 4번 계산시 break
		}
		if (flag == 4)break;
	}
	if (sum > ans) ans = sum;
}

// 인접 블록이 있는지 검색
// 상 하 좌 우에 대하여 한 번이라도 인접 블록이 등장하면 true
bool validity(int r, int c, int visited[510][510]) {
	for (int i = 0; i < 4; i++) {
		// boundary check
		if (r + dr[i] >= 0 && r + dr[i] < N&&c + dc[i] >= 0 && c + dc[i] < M) {
			if (visited[r + dr[i]][c + dc[i]] == 1) return true;
		}
	}
	return false;
}

void back(int depth, int curR, int curC) {
	int maxR = curR + 4;
	int maxC = curC + 4;
	int minC = curC - 4;
	if (minC < 0) minC = 0;

	if (depth == 4) {
		calculate();
		return;
	}

	else {
		if (depth == 0) {
			for (int r = 0; r < N; r++) {
				for (int c = 0; c < M; c++) {
					// depth가 0인 경우는 주변에 블록이 없어도 배치 가능해야함
					visited[r][c] = 1;
					back(depth + 1, r, c);
					visited[r][c] = 3; // 시작점이 반복되지 않게 0이 아닌 값을 표시
					// 시작점이 한 번이라도 들어가면 그 이후론 고려하지 않아도 됨
				}
			}
		}

		// depth가 1 이상이면 주변에 블록이 있어야만 배치 (validity이용)
		// cur는 0부터가야함
		// row는 0부터 가면 중복 발생 -> 전달받은 현재 row로 진행
		else if (depth > 0) {
			for (; curR < maxR; curR++) {
				for (int c = minC; c < maxC; c++) {
					if (visited[curR][c] == 0 && validity(curR, c, visited)) {
						visited[curR][c] = 1;
						back(depth + 1, curR, c);
						visited[curR][c] = 0;
					}
				}
			}
		}
	}
}

djm03178 5년 전 1

매번 back함수가 재귀호출될 때마다 최대 500*500개의 칸을 보게 되는데, 그럴 필요가 있을까요?

validity를 통해 그 칸에 인접한 방문 칸이 있는지를 보고 있는데, 실제로 유효한 칸의 개수는 많아야 8칸 뿐이고 (depth가 3일 때 ㅁㅁㅁ 모양), 나머지 249992칸은 어차피 유효하지 않은 칸인데도 불필요하게 검사를 하게 됩니다.

어떻게 하면 그런 칸들을 아예 보지 않고 백트래킹을 수행할 수 있을지 생각해 보세요.

gun0317 5년 전 0

djm03178님 답변 감사합니다. 코드 수정하였습니다.(수정된 부분: 52~54, 63, 78~85 줄)

제가 63번 줄 'if(depth ==0)'의 위치를 잘못 두었던 것 같아 올바른 위치로 옮겼습니다. 그리고 maxR,maxC 등을 사용하여 본인 근처 4칸만 탐색을 하도록 해 보았으나 여전히 시간초과가 납니다. 500*500칸을 보는 경우는 없어진 것 같은데 여전히 시간초과가 나는 이유를 잘 모르겠습니다..

djm03178 5년 전 2

여전히 16x16칸을 보는 것이 비효율적이기는 하지만, 이제 여기보다 더 문제인 곳은 calculate 함수입니다. 네 칸을 고를 때마다 25만칸씩을 체크해야 하므로 매우 비효율적입니다. 재귀 호출을 할 때마다 어떤 칸을 체크했는지를 미리 모아두면 이렇게 25만 칸을 calculate 함수가 다시 볼 필요가 없습니다.

참고로, 현재 코드가 200x200 칸에서 27번째 줄의 루프가 도는 횟수는 이미 168억이나 됩니다.

gun0317 5년 전 0

djm03178 님 상세한 답변 감사합니다. 문제 풀기만 급급해서 calculate 부분은 볼 생각을 못 했었는데 이부분을 말씀하신대로 vector에 추가하여 접근하니 비록 느리지만 정답처리 되었습니다. 덕분에 많이 배워갑니다. 좋은 하루 되세요!!

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int map[510][510], visited[510][510];
int N, M, ans;
void back(int depth, int curR, int curC);
void calculate();
bool validity(int r, int c, int visited[510][510]);
int dr[] = { -1,1,0,0 }, dc[] = { 0,0,-1,1 };
vector <pair <int, int>> v;

int main() {
	cin >> N >> M;
	for (int r = 0; r < N; r++)
		for (int c = 0; c < M; c++)
			scanf(" %d", &map[r][c]);

	back(0, 0, 0);
	cout << ans << endl;
	return 0;
}

void calculate() {
	int sum = 0;
	for (int i = 0; i < 4; i++) {
		sum += map[v[i].first][v[i].second];
	}

	if (sum > ans) ans = sum;
}

// 인접 블록이 있는지 검색
// 상 하 좌 우에 대하여 한 번이라도 인접 블록이 등장하면 true
bool validity(int r, int c, int visited[510][510]) {
	for (int i = 0; i < 4; i++) {
		// boundary check
		if (r + dr[i] >= 0 && r + dr[i] < N&&c + dc[i] >= 0 && c + dc[i] < M) {
			if (visited[r + dr[i]][c + dc[i]] == 1) return true;
		}
	}
	return false;
}

void back(int depth, int curR, int curC) {
	int maxR = curR + 4;
	int maxC = curC + 4;
	int minC = curC - 4;
	if (minC < 0) minC = 0;

	if (depth == 4) {
		calculate();
		return;
	}

	else {
		if (depth == 0) {
			for (int r = 0; r < N; r++) {
				for (int c = 0; c < M; c++) {
					// depth가 0인 경우는 주변에 블록이 없어도 배치 가능해야함
					visited[r][c] = 1;
					v.push_back(make_pair(r, c));
					back(depth + 1, r, c);
					visited[r][c] = 3; // 시작점이 반복되지 않게 0이 아닌 값을 표시
					v.pop_back();
					// 시작점이 한 번이라도 들어가면 그 이후론 고려하지 않아도 됨
				}
			}
		}

		// depth가 1 이상이면 주변에 블록이 있어야만 배치 (validity이용)
		// cur는 0부터가야함
		// row는 0부터 가면 중복 발생 -> 전달받은 현재 row로 진행
		else if (depth > 0) {
			for (; curR < maxR; curR++) {
				for (int c = minC; c < maxC; c++) {
					if (visited[curR][c] == 0 && validity(curR, c, visited)) {
						visited[curR][c] = 1;
						v.push_back(make_pair(curR, c));
						back(depth + 1, curR, c);
						visited[curR][c] = 0;
						v.pop_back();
					}
				}
			}
		}
	}
}

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

문제

문제

출처

ICPC

백트레킹 함수로 가능한 중복 없이 모든 조합을 만들었는데, 시간 초과가 납니다.

gun0317 5년 전 0

djm03178 5년 전 1

gun0317 5년 전 0

djm03178 5년 전 2

gun0317 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말