글 읽기 - 이 방법으로 풀면 시간초과가 납니다. 조언 부탁드립니다.

opop20207 4년 전 1

DFS1은 홀수칸, DFS2는 짝수칸의 비숍을 계산하는 방법으로

전체 탐색공간을 반으로 나누어 진행했습니다.

이렇게 풀어도 시간안에 맞추기 어려워지나요? 이 코드같은 경우에는 4%에서 멈추더군요...
다르게 푼다면 어떤식으로 풀어야할지 조언 부탁드립니다.

#include <stdio.h>
#define max(a,b) a>b?a:b
int N;
int map[15][15];
int check1[15][15];
int check2[15][15];
int res1, ret1;
int res2, ret2;

void print() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%d ", map[i][j]);
		}
		puts("");
	}
	puts("");
}

bool check(int x, int y) {
	int tempx = x;
	int tempy = y;
	while (true) {
		tempx--; tempy--;
		if (tempx < 0 || tempy < 0) break;
		if (map[tempx][tempy] == 2) return false;
	}
	tempx = x;
	tempy = y;
	while (true) {
		tempx--; tempy++;
		if (tempx < 0 || tempy >= N) break;
		if (map[tempx][tempy] == 2) return false;
	}
	tempx = x;
	tempy = y;
	while (true) {
		tempx++; tempy--;
		if (tempx >= N || tempy < 0) break;
		if (map[tempx][tempy] == 2) return false;
	}
	tempx = x;
	tempy = y;
	while (true) {
		tempx++; tempy++;
		if (tempx >= N || tempy >= N) break;
		if (map[tempx][tempy] == 2) return false;
	}
	return true;
}

void DFS1(int depth) {
	for (int a = 0; a < N * N; a += 2) {
		int i = a / N;
		int j = a % N;
		if (map[i][j] == 1 && check(i, j)) {
			map[i][j] = 2;
			DFS1(depth + 1);
			map[i][j] = 1;
		}
	}
	ret1 = max(depth, ret1);
}

void DFS2(int depth) {
	for (int a = 1; a < N * N; a += 2) {
		int i = a / N;
		int j = a % N;
		if (map[i][j] == 1 && check(i, j)) {
			map[i][j] = 2;
			DFS2(depth + 1);
			map[i][j] = 1;
		}
	}
	ret2 = max(depth, ret2);
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	DFS1(0);
	DFS2(0);
	printf("%d\n", ret1 + ret2);
}

opop20207 4년 전 0

1만 탐색할것이니 1인 부분은 미리 담아둔후 해결한다는 방법으로

아래와 같이 해결했습니다만 위코드에 대한 미련이 남네요.

위코드는 해결할 수 없는지 궁금합니다.

#include <stdio.h>
#define max(a,b) a>b?a:b
typedef struct mystruct {
	int X;
	int Y;
}XY;
XY black[55], white[55];
int N;
int map[15][15];
int wmax, bmax, widx, bidx;

void print() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%d ", map[i][j]);
		}
		puts("");
	}
	puts("");
}

bool check(int x, int y) {
	int tempx = x;
	int tempy = y;
	while (true) {
		tempx--; tempy--;
		if (tempx < 0 || tempy < 0) break;
		if (map[tempx][tempy] == 2) return false;
	}
	tempx = x;
	tempy = y;
	while (true) {
		tempx--; tempy++;
		if (tempx < 0 || tempy >= N) break;
		if (map[tempx][tempy] == 2) return false;
	}
	tempx = x;
	tempy = y;
	while (true) {
		tempx++; tempy--;
		if (tempx >= N || tempy < 0) break;
		if (map[tempx][tempy] == 2) return false;
	}
	tempx = x;
	tempy = y;
	while (true) {
		tempx++; tempy++;
		if (tempx >= N || tempy >= N) break;
		if (map[tempx][tempy] == 2) return false;
	}
	return true;
}

void DFS(XY* a, int num, int size, int depth, int *maxx) {
	for (int i = num; i < size; i++) {
		int x = a[i].X;
		int y = a[i].Y;
		if (check(x, y)) {
			map[x][y] = 2;
			DFS(a, i + 1, size, depth+1, maxx);
			map[x][y] = 1;
		}
	}
	*maxx = max(depth, *maxx);
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1d", &map[i][j]);
			if (map[i][j] == 1) {
				if ((i + j) % 2 == 0) {
					white[widx++] = { i,j };
				}
				else {
					black[bidx++] = { i,j };
				}
			}
		}
	}
	DFS(white, 0, widx, 0, &wmax);
	DFS(black, 0, bidx, 0, &bmax);
	printf("%d\n", wmax + bmax);
}

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

문제

문제

출처

ICPC

이 방법으로 풀면 시간초과가 납니다. 조언 부탁드립니다.

opop20207 4년 전 1

opop20207 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말