[백준 2580] 스도쿠

아이디어

• 완전탐색(브루트포스)를 사용할 줄 안다
• 얕은 복사(&)로 함수 인자를 넘겨줄 수 있다

접근방식

1. 숫자를 기입하되 가로줄,세로줄,큰 박스에 set을 만들어 숫자를 저장해준다
2. dfs를 돌되, 꼭 '얕은복사'로 비어있는 칸에 해당하는 vector를 넘겨준다
3. 1~9까지 반복하며 가로줄,세로줄,큰 박스 모두에 해당 숫자가 없으면 각각 set, 배열에 넣어주고 dfs를 들어간다. 그 이후 다음 dfs를 위해 다시 처음 값으로 초기화 해준다.
4. 만약 position이 blanks.size()일 경우 모든 칸을 다 조사하고 채웠다고 판단이 되므로, 스도쿠를 출력해준다.

#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<unordered_set>
#include<set>
using namespace std;

int board[9][9];
int get_answer = false;
unordered_set<int> bigbox[3][3];
unordered_set<int> rowline[9];
unordered_set<int> colline[9];

void dfs(vector<pair<int, int>> &blanks,int pos) {
	if (get_answer == true) return;

	if (pos == blanks.size()) {
		get_answer = true;

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << board[i][j] << " ";
			}
			cout << endl;
		}

		return;
	}

	int now_row = blanks[pos].first;
	int now_col = blanks[pos].second;

	for (int i = 1; i <= 9; i++) {
		if (bigbox[now_row / 3][now_col / 3].count(i) == 0 && rowline[now_row].count(i) == 0 && colline[now_col].count(i) == 0) { //만약 전부 없으면 넣기

			bigbox[now_row / 3][now_col / 3].insert(i);
			rowline[now_row].insert(i);
			colline[now_col].insert(i);
			board[now_row][now_col] = i;

			dfs(blanks, pos + 1);

			bigbox[now_row / 3][now_col / 3].erase(i);
			rowline[now_row].erase(i);
			colline[now_col].erase(i);
			board[now_row][now_col] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	vector<pair<int, int>> blanks;

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			int num; cin >> num;
			if (num == 0) blanks.push_back({ i,j });
			else {
				bigbox[i / 3][j / 3].insert(num);
				rowline[i].insert(num);
				colline[j].insert(num);
			}
			board[i][j] = num;
		}
	}

	dfs(blanks, 0);
	

	return 0;
}

평가

얕은복사를 꼭 알아야하는 문제!!!
문제 구현에는 20분 정도밖에 소요되지 않았지만,
85%에서 자꾸 시간초과가 나서 애를 먹었던 문제입니다.
시간초과가 난 이유는 함수에 인자를 넘겨줄때 깊은복사 로 넘겨줄 경우
계속해서 그 값을 복사를 하기 때문에 시간초과가 계속 난 것이었습니다.
vector<pair<int, int>> blanks 에서 vector<pair<int, int>> &blanks 로 바꿔주니 거짓말같이 통과하는 것을 확인할 수 있었습니다.
왠만한 문제에서는, 벡터를 넘겨줄때 전역변수로 선언하거나, 얕은복사로 주소값만 넘겨주는 것이 시간해결에 좋은 방법인 것 같습니다.

배울 것

• 함수 인자로 넘겨줄 때 꼭 '얕은복사' 를 생각해주자!!