글 읽기 - 2580 질문입니다.

chatterboy 8년 전 0

0인 위치를 저장해두고 각 위치에 대해서 백트래킹을 이용해서 풀었습니다.

TLE인데 시간을 더 줄일 수 있을까요?

#include <cstdio>
#include <vector>
using namespace std;
#define n 9

int m, bd[n+1][n+1];
vector<int> x, y;

bool can(int pos) {
	int temp[10] = {0};
	for(int j=1; j<=n; ++j)
		if(bd[y[pos]][j]!=0 && temp[bd[y[pos]][j]]++ == 1)
			return false;

	int temp2[10] = {0};
	for(int i=1; i<=n; ++i)
		if(bd[i][x[pos]]!=0 && temp2[bd[i][x[pos]]]++ == 1) 
			return false;

	int temp3[10] = {0};
	for(int i=1; i<=n; i+=3)
		for(int j=1; j<=n; j+=3)
			if(i<=y[pos]&&y[pos]<i+3 && j<=x[pos]&&x[pos]<j+3)
				for(int ii=i; ii<i+3; ++ii)
					for(int jj=j; jj<j+3; ++jj)
						if(bd[ii][jj]!=0 && temp3[bd[ii][jj]]++ == 1)
							return false;
	return true;
}

bool solve(int pos) {
	if(pos > m)
		return true;
	for(int num=1; num<=9; ++num) {
		bd[y[pos]][x[pos]] = num;
		if(can(pos))
			if(solve(pos+1))
				return true;
		bd[y[pos]][x[pos]] = 0;
	}
	return false;
}

int main() {
	x.push_back(-1); y.push_back(-1);
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=n; ++j) {
			scanf("%d", &bd[i][j]);
			if(bd[i][j] == 0) {
				x.push_back(j);
				y.push_back(i);
			}
		}
	m = x.size()-1;
	solve(1);
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) printf("%d ", bd[i][j]);
		putchar('\n');
	}
}

yukariko 8년 전 0

가로, 세로, 3*3 칸에 대한 정보를 가지고 있으면

can 함수를 대략 한번의 연산으로 구할 수 있습니다.

chatterboy 8년 전 0

@yukariko 오예! 감사합니다 !

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

문제

문제

출처

ICPC

2580 질문입니다.

chatterboy 8년 전 0

yukariko 8년 전 0

chatterboy 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말