글 읽기 - 1941 소문난 칠공주 최적화 질문있습니다.

10jobss 6년 전 0

2^25 경우에 대해

길이가 7이 아니거나 S그룹의 수가 4보다 작은경우
그룹이 연결되어 있지 않은 경우

제외하는 로직입니다.

아래 코드의 경우 시간초과, 주석을 제거고 제출할 경우 1952ms로 맞았습니다.

주석 처리된 부분이 시간에 크게 영향 미치진 않다고 생각했는데 통과된 이유가 무엇일까요?

#include <cstdio>
#include <cstring>
int ans;
char c[5][5];
int chk[25];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void dfs(int y, int x) {
	chk[y * 5 + x] = 3;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= 0 && ny < 5 && nx >= 0 && nx < 5 && chk[ny * 5 + nx]==2) {
			dfs(ny, nx);
		}
	}
}
int main() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) scanf(" %c", &c[i][j]);
	}
	for (int i = 0; i < (1 << 25); i++) {
		int len = 0, ss = 0;
		bool bb = true;
		for (int j = 0; j < 25; j++) {
			if (i&(1 << j)) {
				if (c[j / 5][j % 5] == 'S') ss++;
				len++;
			}
			/*if (len > 7) {
				bb = false;
				break;
			}*/
		}
		//if (!bb) continue;
		if (len != 7 || ss < 4) continue;
		memset(chk, 0, sizeof(chk));
		int idx = 0, g[7] = { 0 };
		for (int j = 0; j < 25; j++) {
			if (i&(1 << j)) {
				g[idx++] = j;
				chk[j] = 2;
			}
		}
		dfs(g[0] / 5, g[0] % 5);
		bool flag = true;
		for (int j = 0; j < 7; j++) {
			if (chk[g[j]] != 3) {
				flag = false;
				break;
			}
		}
		if (!flag) continue;
		ans++;
	}
	printf("%d", ans);
	return 0;
}