[백준/C++] 2580 스도쿠 (G4)

https://www.acmicpc.net/problem/2580

 

유형	난이도	완료일	특이사항
백트래킹	골드4	23/02/05

 

<내 코드> - 230205

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<pair<int,int>> pair_vec;
vector<int> number_guide;

vector<int> row_vec;   //*** 재귀함수 안에서 선언했을 때는 시간초과 받음 ***
vector<int> column_vec;
vector<int> box_vec; 

int arr[9][9]; //스도쿠 배열
//int 

void Recursion(int pair_idx, int depth)
{
	if(depth == pair_vec.size()) //같아지면 모든 칸을 채운 것 -> 가능한 후보로 모든 칸을 채울 수 밖에 없으므로 출력하면 끝
	{
		for(int i = 0; i< 9; i++)
		{
			for(int j =0; j<9; j++)
			{
				cout << arr[i][j]<<" ";
			}
			cout << "\n";
		}
		
		exit(0);
	}
	
	int row = pair_vec[pair_idx].first;
	int column = pair_vec[pair_idx].second;
		
	row_vec.clear();
	column_vec.clear();
	box_vec.clear();
	
	vector<int> final_vec(10);
	
	for(int i =0; i< 9; i++)
	{
		if(i==column)
			continue;
		
		if(arr[row][i]!=0) //존재하는 수를 후보에서 제외하기 위해 vector에 담아준다.
		{
			row_vec.emplace_back(arr[row][i]);
		}
	}
	
	sort(row_vec.begin(), row_vec.end());
	auto iter1 = set_difference(number_guide.begin(), number_guide.end(), row_vec.begin(),row_vec.end(), final_vec.begin());
	final_vec.erase(iter1, final_vec.end()); // row에서 후보 숫자들 저장
	
	for(int i =0; i< 9; i++)
	{
		if(i==row)
			continue;
		
		if(arr[i][column]!=0) //존재하는 수를 후보에서 제외하기 위해 vector에 담아준다.
		{
			column_vec.emplace_back(arr[i][column]);
		}
	}
	
	sort(column_vec.begin(), column_vec.end());
	auto iter2 = set_difference( final_vec.begin(), final_vec.end(), column_vec.begin(), column_vec.end(), final_vec.begin());
	final_vec.erase(iter2, final_vec.end()); 
	/// row, column의 후보들 저장완료
	
	int box_row = row/3;
	int box_column = column/3;
	
	for(int i=box_row*3; i<box_row*3+3; i++)
	{
		for(int j=box_column*3; j<box_column*3+3; j++)
		{
			if(i==row && j==column)
				continue;
			
			if(arr[i][j]!=0)
			{
				box_vec.emplace_back(arr[i][j]);
			}
		}		
	}
	
	sort(box_vec.begin(), box_vec.end());
	auto iter3= set_difference(final_vec.begin(), final_vec.end(), box_vec.begin(), box_vec.end(), final_vec.begin());
	final_vec.erase(iter3, final_vec.end());

	
	
	for(int i = 0; i < final_vec.size(); i++)
	{
		
		arr[row][column] = final_vec[i];
		
		Recursion(pair_idx+1, depth+1);
		
		arr[row][column] = 0;
		
	}
}



int main(void)
{	
	for(int i=1;i<10;i++)
		number_guide.emplace_back(i);
	
	for(int i = 0; i < 9; i++)
	{
		for(int j = 0; j< 9 ; j++)
		{
			cin >> arr[i][j];   
			if(arr[i][j] == 0)
				pair_vec.emplace_back(make_pair(i,j)); //0의 좌표를 저장
		}
	}
	
	
	Recursion(0,0);

}

답은 맞게 나오는 듯 했으나 83%에서 시간초과를 받았다. 이것저것 시간 단축과 관계된 것들을 수정했지만, 결과적으로 Recursion 함수 안에서

vector<int> row_vec;   
vector<int> column_vec;
vector<int> box_vec; 

이 세 벡터를 선언하던 것을 없애고 전역으로 선언하여 clear()를 이용해 재사용 하는 방식으로 바꾸자 시간 안에 통과할 수 있었다. 함수가 여러번 호출될 수 밖에 없는 재귀함수를 이용한 풀이에서는 deep copy가 자주 일어나는 것을 방지해야 한다.

문제의 기본 해결 아이디어는 채워야 하는 칸 (입력으로 0이 주어지는 좌표)을 모두 저장해두고

해당 좌표의 수직, 3*3크기의 구역을 검사하며 해당 칸에 후보로 가능한 숫자들을 저장하는 것이다.

이렇게 저장된 수들을 하나씩 넣고, 넣은 후엔 다음 채워야 하는 칸으로 이동해 위의 과정을 반복한다.

이런 방식으로 가능한 모든 후보 숫자를 넣어보다가 모든 숫자가 채워지면 그대로 출력 후 프로그램을 종료하면 되고, 가능한 숫자 후보가 없어 그냥 종료되면 다시 이전 좌표로 돌아와 해당 칸에 다른 후보를 넣고 반복한다(DFS).

모든 경우의 수를 빠지지 않고 탐색 가능하며 도중에 가장 먼저 발견되는 가능한 경우의 수를 출력하고 종료한다.