글 읽기 - 1799 시간초과

park03851 5년 전 0

어떻게 해야 시간을 줄일 수 있을까요...

#include <cstdio>
#include <iostream>
using namespace std;

int n, v[11][11], maxx = 0;

int check(int y, int x) {  //경로에 걸리는게 있는지 확인
	int ty, tx;
	
	ty = y;
	tx = x;
	while (1) {
		ty--;
		tx--;
		if (ty < 0 || tx < 0) break;
		if (v[ty][tx] == 2) return -1;
	}
	ty = y;
	tx = x;
	while (1) {
		ty--;
		tx++;
		if (ty < 0 || tx >= n) break;
		if (v[ty][tx] == 2) return -1;
	}
	ty = y;
	tx = x;
	while (1) {
		ty++;
		tx++;
		if (ty >= n || tx >= n) break;
		if (v[ty][tx] == 2) return -1;
	}
	ty = y;
	tx = x;
	while (1) {
		ty++;
		tx--;
		if (ty >= n || tx < 0) break;
		if (v[ty][tx] == 2) return -1;
	}

	return 1;
}

void go(int y, int x, int c) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (v[i][j] == 1 && check(i, j) == 1) {
				v[i][j] = 2;
				go(i, j, c + 1);
				v[i][j] = 1;
			}
		}

	if (maxx < c) {
		maxx = c;
		return;
	}
}

int main() {
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) scanf("%d", &v[i][j]);

	go(0, 0, 0);

	printf("%d", maxx);

	return 0;
}

pda_pro12 5년 전 2

비숍의 특성을 활용하면 현상태가 흰색 칸인지 검은색칸인지로 나뉘어서 각 경우의 수를 계산한다음

합해주기만하면 됩니다.

현재 작성하신 로직은 전체칸에 대해서 경우의수를 한번에 탐색해주는 걸로 보입니다만

흰색칸일 경우와 검은색 칸일경우를 분할하여 생각하시면 현재 복잡도의 n/2이상으로 줄일수 있을 것 같습니다.

park03851 5년 전 0

mulijoa pda_pro12

두분 다 댓글 너무너무 감사합니다. 말해주신 것들로 아이디어를 얻어서 문제를 해결했습니다.
너무 너무 감사드립니다!

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

문제

문제

출처

ICPC

1799 시간초과

park03851 5년 전 0

pda_pro12 5년 전 2

park03851 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말