[백준] 2580번 스도쿠 c++

www.acmicpc.net/problem/2580

2580번: 스도쿠

참고 :yabmoons.tistory.com/88

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

0	1	2
3	4	5
6	7	8

 

코드

• Step1) ROW, COL 배열에 각각 True, False값을 넣어준다
  • ROW[i][map[i][j]]=true
    • 각 행에 사용한 숫자(=map[i][j]))를 체크해준다
  • COL[j][map[i][j]]=true;
    • 각 열에 사용한 숫자를 체크한다.
  • Square[(i/3)*3 + (j/3)][map[i][j]] = true
    • (i/3)*3 + (j/3)
      
      • (i,j)가 상위 표에서 어느 위치에 있는지 알려줌
        • ex) (4,2)
          • (4/3) * 3+ 2/3 = 3 번째 위치
        • ex) (7,7)
          • (7/3)*3 + 7/3 = 8번째 위치
  • dfs에서의 cnt
    • int x = cnt/9;
      • cnt=0~8
        • x=0
        • y=0~9
      • cnt= 9~17
        • x=1
        • y=0~9
      • cnt=18~26
        • x=2...
        • y=0~9...
    • 따라서 cnt=81 이란 것은 (0,0)부터 (9,9)까지 다 돈 것이다.
• 중요한 검색 로직!!

if (map[x][y] == 0)
	{
		for (int i = 1; i <= 9; i++)
		{
			if (row[x][i] == false && col[y][i] == false && square[(x / 3) * 3 + (y / 3)][i] == false)
			{

• 재귀 로직
  • 들어갈 수 있는 가장 작은 i 값을 넣고 다 뺀뒤에 다 그다음 값을 넣고 돌리고 하는 식..!

row[x][i] = true;
col[y][i] = true;
square[(x / 3) * 3 + (y / 3)][i] = true;
map[x][y] = i;
dfs(cnt + 1);
map[x][y] = 0;
row[x][i] = false;
col[y][i] = false;
square[(x / 3) * 3 + (y / 3)][i] = false;

 

• map[i][j] = 0 을 만났을 때
• 해당 가로줄 검사
• 해당 세로줄 검사
• 해당 블럭(9개중1개) 검사
  • 가능한 숫자 입력

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 9
/*
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0  
*/

using namespace std;

void solution()
{

}
int map[9][9];
bool row[9][9];
bool col[9][9];
bool square[9][9];
void Print()
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
}



void dfs(int cnt)
{//cnt : 
	int x = cnt / 9;//x좌표
	int y = cnt % 9;//y좌표
	if (cnt == 81)
	{
		Print();
		exit(0);
	}

	if (map[x][y] == 0)
	{
		for (int i = 1; i <= 9; i++)
		{
			if (row[x][i] == false && col[y][i] == false && square[(x / 3) * 3 + (y / 3)][i] == false)
			{
				row[x][i] = true;
				col[y][i] = true;
				square[(x / 3) * 3 + (y / 3)][i] = true;
				map[x][y] = i;
				dfs(cnt + 1);
				map[x][y] = 0;
				row[x][i] = false;
				col[y][i] = false;
				square[(x / 3) * 3 + (y / 3)][i] = false;
			}

		}

	}
	else dfs(cnt + 1);




}
int main()
{
 


	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> map[i][j];
			if (map[i][j] != 0)
			{
				row[i][map[i][j]] = true; //i번째 가로줄에 n라는 숫자가 이미 존재합니다.
				col[j][map[i][j]] = true; //j번째 세로줄에 n라는 숫자가 이미 존재합니다.
				square[(i / 3) * 3 + (j / 3)][map[i][j]] = true; //a번째 사각형에 b라라는 숫자가 이미존재합니다.

			}
		}
	}

	
	dfs(0);

	return 0;
}