[DFS] 2580 스도쿠 C++

접근법

백트래킹, DFS로 풀이했다.

처음 문제를 시도했을 때 (에러 있음)

우선 코드부터 보자면

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

/// <summary>
/// 답은 나오는데 메모리 초과남 ;;;
/// </summary>

int g[10][10];

int fx = -1;
int fy = -1;

int zidx[10][10] = { 0, };
int zeros = 0;


//queue<pair<int, int>> q;

void dfs(int cnt, int x, int y)
{

	int w[10] = { 0, };
	int h[10] = { 0, };
	int r[10] = { 0, };
	int use[10] = { 0, };

	int nx = -1;
	int ny = -1;

	int flag = 0;
	if (cnt == zeros+1) 
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				cout << g[i][j] << " ";
			}
			cout << endl;
		}
		return;
	}

	// 확인용 배열에 값 넣기
	for (int i = 0; i < 9; i++)
	{
		w[g[x][i]] = 1;
		h[g[i][y]] = 1;
	}

	// xpos , ypos 가 어떤 방에 있는지
	int xpos = (x / 3) * 3;
	int ypos = (y / 3) * 3;

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			r[g[xpos + i][ypos + j]] = 1;
		}
	}

	// 중복 확인 ( 가로줄, 세로줄, 방 )
	for (int i = 1; i < 10; i++)
	{
		// 해당 x, y 의 가로줄, 세로줄, 방에 i 라는 숫자가 없다면 use[i]에 1 더함
		if (w[i] == 0)
			use[i] += 1;
		if (h[i] == 0)
			use[i] += 1;
		if (r[i] == 0)
			use[i] += 1;
	}

	// 다음 x, y 계산
	
	for (int i = x * 9 + y; i < 81; i++)
	{
		if (zidx[i/9][i%9] == 1)
		{
			zidx[i/9][i % 9] = 0;
			nx = i / 9;
			ny = i % 9;
			flag = 1;
			break;
		}
		
		if (flag == 1)
			break;
	}


	// use 배열안에 값이 3이면 가로, 세로, 방 안에 없는 숫자이기 때문에 대입한다. ( 3이 아니면 안됨 )
	 
	for (int i = 1; i < 10; i++)
	{
		if (use[i] == 3)
		{
			g[x][y] = i;
			dfs(cnt + 1, nx, ny);
			zidx[nx][ny] = 1;
			g[x][y] = 0;
		}
	}
}

// 가로 세로에 중복되는 숫자가 없어야 하며, 빈칸이 속한 방 안에 숫자가 중복되지 않아야 한다.

int main()
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> g[i][j];

			if (fx == -1 && fy == -1 && g[i][j] == 0)
			{
				fx = i;
				fy = j;
			}

			if (g[i][j] == 0)
			{
				zidx[i][j] = 1;
				zeros++;
			}
		}
	}

	cout << endl;

	zidx[fx][fy] = 0;

	dfs(1, fx, fy);


	return 0;
}

이렇게 풀이를 했는데 메모리 초과에 OutofBound에 아주 난리가 났었다.

결국 코드를 처음부터 다시 짜게 되었는데

1. dfs 를 시작하면
   좌표랑 카운트를 받고 시작한다

2. 조건 검사
   • 해당 좌표에 들어갈 숫자가 있는지 확인하고 들어갈 수 없다면 return

3.반복문
- 해당 좌표에 들어갈 수 있는 숫자를 for문을 통해 넣는다.

• 나왔을 때
  - 0으로 바꿔줘야됨

그러면 for 문을 통해서 다음 dfs를 진행할 때 빈칸에 넣을 숫자를 dfs에 넣어서 진행하는데

1. 일단 넣어서 진행하고 거기서 중복되는 숫자가 있으면 return 하도록?
2. 애초에 가로 세로 방 안에 없는 숫자를 넣으면서 return 하도록?

이 두가지로 생각을 했다. 일단 넣고 return 하는 편이 조건 검사를 하기도 편하다고 생각해서
1번을 택해 진행했고 성공했다.

스도쿠에서 빈칸이 들어가는 좌표는 vector에 pair로 저장했고

• 종료 조건검사,
• 입력으로 들어온 값이 빈칸에 들어갈 수 있는지 조건 검사,
• 빈칸 대입
  순으로 진행한다.

최종 코드

#include <bits/stdc++.h>

#define endl "\n"

using namespace std;

int g[10][10] = { 0, };
int p = 0;
// 0의 좌표를 저장하는 벡터
vector<pair<int, int>> v;

void dfs(int cnt, int x, int y, int val)
{
	// 멈춤 조건
	if (cnt == v.size() - 1 && p == 0)
	{
		cout << endl;
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				cout << g[i][j] << " ";
			}
			cout << endl;
		}
		p = 1;
		exit(0);
	}

	// val이 빈칸에 들어갈 수 있는 숫자인지 확인
	for (int i = 0; i < 9; i++)
	{
		if (g[x][i] == val)
			return;
		if (g[i][y] == val)
			return;
	}

	int xpos = (x / 3) * 3;
	int ypos = (y / 3) * 3;

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (g[xpos + i][ypos + j] == val)
				return;
		}
	}

	// 여기까지 왔으면 넣을 수 있는 숫자인거임.

	g[x][y] = val;

	int nx = v[cnt + 1].first;
	int ny = v[cnt + 1].second;

	for (int i = 1; i <= 9; i++)
	{
		dfs(cnt + 1, nx, ny, i);
		g[nx][ny] = 0;
	}
}


int main()
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> g[i][j];

			if (g[i][j] == 0)
				v.push_back(make_pair(i, j));
		}
	}

	v.push_back(make_pair(0, 0));

	for (int i = 1; i <= 9; i++)
	{
		if ( p == 0 )
			dfs(0, v.front().first, v.front().second, i);
	}

	return 0;
}

후기

처음에는 분명 내 컴퓨터에서는 잘 작동 됐는데 시간초과, 메모리초과가 나는 이유를 몰랐는데
dfs를 들어가면서 이중for문이 9x9 판을 전부 검사한다.
이 부분에서 너무 쓸데없는 검사를 해버리는 탓에 시간초과가 났다.


다른 게시글에서는 이중 for문을 for 하나로 쓰면 시간초과가 안난다. 검사에 조건을 추가하면 된다.
등등 글을 여러개 봤지만 사실 아무것도 안됐었고
처음부터 구조를 다시 생각해서 풀어야 했다.

쉬운 문제인것 같은데 이틀이나 시행착오 끝에 풀었다는게 아직도 많이 어설프다는게 느껴졌다.