글 읽기 - 스도쿠 시간 초과 문제

psujin22 3년 전 0

오늘 하루 종일 이거랑 씨름하는데..

시간초과 났다가.. 틀렸다가를 반복하고 있습니다.

ㅠ.ㅠ

혹시 이 구조 자체가 시간이 오래 걸리는 구조일까요?

아니면 여기에서 조금만 수정하면 되는 걸까요?

비어있는 부분을 골라 다니며 세로 가로줄 작은 네모의 값을 계산하고 있습니다.

도움이 필요합니다.. ㅠ.ㅠ 미리 감사드려요 ㅠ.ㅠ

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <stack>

using namespace std;

struct A
{
	int x;
	int y;
	bool operator<(const A& n) const
	{	// apply operator< to operands
		if (x == n.x) return (y < n.y);
		return (x < n.x);
	}
};
set<A> zero;

int board[9][9];
int N;
int valueCol[9];
int valueRow[9];
int valueSqr[9][9];

int zvalueCol[9];
int zvalueRow[9];
int zvalueSqr[9][9];

bool calcValue(int x, int y)
{
	int i, j, sum = 0, blockx, blocky, check = 0;
	blockx = (x / 3) * 3; 
	blocky = (y / 3) * 3;
	//가로
	if(zvalueRow[x] == 1)
	{
		board[x][y] = 45 - valueRow[x];
		//valueRow[x] = 45;
		//zvalueRow[x]--;

		valueCol[y] += board[x][y];
		valueSqr[blockx][blocky] += board[x][y];

		zvalueCol[y]--;
		zvalueSqr[blockx][blocky]--;
		return true;
	}

	//세로
	if(zvalueCol[y] == 1)
	{
		board[x][y] = 45 - valueCol[y];
		//valueCol[y];
		//zvalueCol[y]--;

		valueRow[x] += board[x][y];
		valueSqr[blockx][blocky] += board[x][y];


		zvalueRow[x]--;
		zvalueSqr[blockx][blocky]--;

		return true;
	}

	//작은 네모
	if(zvalueSqr[blockx][blocky] == 1)
	{
		board[x][y] = 45 - valueSqr[blockx][blocky];
		//valueSqr[blockx][blocky] = 45;
		//zvalueSqr[blockx][blocky]--;
		
		valueCol[y] += board[x][y];
		valueRow[x] += board[x][y];

		zvalueCol[y]--;
		zvalueRow[x]--;
		return true;
	}
	return false;
}

int main(void)
{
	int i, j;
	int n;

	N = 9;

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			cin >> n;
			board[i][j] = n;
			if (board[i][j] == 0)
			{
				A a = { i, j };
				zero.insert(a);

				zvalueRow[i]++;
				zvalueCol[j]++;

				zvalueSqr[((i / 3) * 3)][((j / 3) * 3)]++;
			}
			valueRow[i] += n;
			valueCol[j] += n;

			valueSqr[((i / 3) * 3)][((j / 3) * 3)] += n;
		}
	}

	while (zero.size())
	{
		set<A>::iterator iter = zero.begin();
		for (; iter != zero.end();)
		{		
			if (calcValue((*iter).x, (*iter).y))
			{
				//지워야 되는데.... 
				iter = zero.erase(iter);
			}
			else iter++;
		}
		/*for (i = 0; i < N; i++)
		{
			for (j = 0; j < N; j++)
			{
				cout << board[i][j] << " ";
			}
			cout << "\n";
		}
		cout << "\n";*/
	}


	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			cout << board[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";

	return 0;

}

psujin22 3년 전 0

자문 자답이지만..

참으로 많이 부족한 나임을 깨닫게 되네요

더 공부 해야 할 것 같습니다.

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <stack>

using namespace std;

int board[9][9];
int N;

int check[9][9];
int checkLength = 0;

int check2(int x, int y, int v)
{
	int i, j, sum = 0, blockx, blocky, check = 0;
	blockx = (x / 3) * 3;
	blocky = (y / 3) * 3;

	//가로
	for (i = 0; i < 9; i++)
	{
		if(board[x][i] == v) return false;
	}

	//다 달랐다면... 
	//세로
	for (i = 0; i < 9; i++)
	{
		if (board[i][y] == v) return false;
	}

	for (i = blockx; i < blockx + 3; i++)
	{
		for (j = blocky; j < blocky + 3; j++)
		{
			if (board[i][j] == v) return false;
		}
	}

	return true;
}
int stop;

void f(int x, int y)
{
	int i, j;

	//cout << "x = " << x << ", y = " << y << "\n";

	if (x == 9 && y == 0)
	{
		for (i = 0; i < N; i++)
		{
			for (j = 0; j < N; j++)
			{
				cout << check[i][j] << " ";
			}
			cout << "\n";
		}
		cout << "\n";

		stop = 1;
		return;
	}
	
	if (board[x][y] != 0)
	{
		if (y == 8) f(x + 1, 0);
		else f(x, y + 1);
		return;
	}
	for (i = 1; i < 10; i++)
	{
		//cout << x << " " << y << " " << i << "\n";

		 // i가 들어갈 수 있는 경우라면
			if (check2(x, y, i))
			{
				board[x][y] = i;
				check[x][y] = i;
				if (y == 8) f(x + 1, 0);
				else f(x, y + 1);
				board[x][y] = 0;
			}
			if (stop == 1)
				return;
	}
}

int main(void)
{
	int i, j;
	int n;

	N = 9;

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			cin >> n;
			board[i][j] = n;
			check[i][j] = n;
		}
	}

	stop = 0;
	f(0, 0);

	return 0;

}

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

문제

문제

출처

ICPC

스도쿠 시간 초과 문제

psujin22 3년 전 0

psujin22 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말