[백준 알고리즘] 2239번 스도쿠 문제풀이

DFS를 활용한 스도쿠 문제풀이이다.

 

list벡터에 보드가 0일때 위치, 즉 1~9값이 채워져야하는 곳의 위치를 저장한다

DFS의 인자 level은 list벡터의 index위치이고, value는 1~9값 중 하나를 뜻한다

i가 0~9일 때,

board[nx][i](가로)

board[i][ny](세로)

, board[nx/3*3+i/3][ny/3*3+i%3](3*3 정사각형)

이 value값인지 확인하고 가로,세로,3*3정사각형에 같은 value가 있다면 해당 dfs를 종료한다.

아니라면 해당 level 위치의 board값을 value로 하고,

level+1이면서 value 0~9일 때 DFS를 호출한다.

 

level이 list.size()-1이면 스도쿠를 다 채웠을 때이므로,

결과값을 출력한 후 exit(0)을 호출하여 프로그램을 종료한다.

 

#include <iostream>
#include <vector>

using namespace std;

int board[9][9];

struct pos{
	int x;
	int y;
	pos(int a, int b){
		x =a;
		y =b;
	}
};
vector<pos> list;

void DFS(int level, int value){
	int nx =list[level].x;
	int ny =list[level].y;
	for(int i=0; i<9; i++)
		if(board[nx][i] == value || board[i][ny] == value ||
				board[nx/3*3+i/3][ny/3*3+i%3] == value)
			return;
	if(level == list.size()-1){
		board[nx][ny] = value;
		for(int i=0; i< 9; i++){
			for(int j=0; j<9; j++){
				cout << board[i][j];
			}
			cout << endl;
		}
		exit(0);
	}
	else{
		for(int i=1; i<=9; i++){
			board[nx][ny] = value;
			DFS(level+1, i);
			board[nx][ny] = 0;
		}
	}
}

int main(){

	char input;
	for(int i=0; i< 9; i++){
		for(int j=0; j<9; j++){
			cin >> input;
			board[i][j] = input -'0';
			if(board[i][j]==0){
				list.push_back(pos(i,j));
			}
		}
	}
	for(int i=1; i<=9; i++){
		DFS(0, i);
	}
}