BOJ: 스도쿠(2580) [C++]

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

2580번: 스도쿠

 

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

 

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

 

복붙에 삼만년이 걸렸는데 진짜 그냥 스도쿠

살다살다 스도쿠도 코딩을 하고...

 

일단 조건이 한 행에 같은 숫자 안됨 / 한 열에 같은 숫자 안됨 / 3x3 안에 같은 숫자 안됨

3x3 구역은 이런식으로 짤릴테니까

const int MAX = 9;
//check[a][b] -> a행/열/구역에 숫자 b가 존재함
bool check_row[MAX][MAX + 1]; //각 행에서 중복 체크
bool check_col[MAX][MAX + 1]; //각 열
bool check_3x3[MAX][MAX + 1]; //각 3x3사각형
int get3x3Idx(int row, int col) {
	return (row / 3) * 3 + (col / 3);
}

이런식으로 일단 사전작업을...

 

bool fillSudoku(int idx, vector<vector<int>>* sudoku) {
	if (idx == MAX * MAX) return true;
	int row = idx / MAX;
	int col = idx % MAX;
	if ((*sudoku)[row][col]) { //이미 채워진 칸이면 다음으로
		return fillSudoku(idx + 1, sudoku);
	}
	for (int i = 1; i <= MAX; i++) {
		//1~9까지 넣어보면서 조건 만족하나 확인
		if (!check_row[row][i] && !check_col[col][i] && !check_3x3[get3x3Idx(row, col)][i]) {
			//만족하면 해당칸에 숫자 들어갈 수 있음
			//체크 배열에 표기
			check_row[row][i] = true;
			check_col[col][i] = true;
			check_3x3[get3x3Idx(row, col)][i] = true;
			//스도쿠 칸 채우기
			(*sudoku)[row][col] = i;

			if (fillSudoku(idx + 1, sudoku)) {
				return true;
			}

			//체크 배열 다시 수정, 스도쿠 칸 비우기
			check_row[row][i] = false;
			check_col[col][i] = false;
			check_3x3[get3x3Idx(row, col)][i] = false;
			(*sudoku)[row][col] = 0;
		}
	}
	return false;
}

vector<vector<int>> solution(vector<vector<int>>sudoku) {
	vector<vector<int>>answer(MAX, vector<int>(MAX));
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			answer[i][j] = sudoku[i][j];
			if (sudoku[i][j]) {
				check_row[i][sudoku[i][j]] = true;
				check_col[j][sudoku[i][j]] = true;
				check_3x3[get3x3Idx(i, j)][sudoku[i][j]] = true;
			}
		}
	}
	fillSudoku(0, &answer);
	return answer;
}

풀 수 있는 입력만 주어진다고 했다

 

일단 원리자체는 단순하다 1부터 9까지 넣어보면서 되면 넣고 아님 말고 <- 이거다

일단 해당 숫자에 대해 check_row, check_col, check_3x3이 모두 false라면 그 칸에 들어갈 수 있는 거니까, 칸에 숫자를 넣어주고 check배열 값들을 true로 세팅한다.

그리고 인덱스를 1 늘려 fillSudoku를 다시 출력한다. 만약 이후에도 쭉 만족한다면 계속계속 채워질 것이고, 만약 만족하지 않는 순간이 온다면(채울 수 없다면) check배열과 sudoku 칸을 원래대로 돌려줘야 한다.

 

solution함수에서는 우선 입력받은 스도쿠 배열을 가지고 check배열과 answer 벡터를 세팅해준다.

그리고나서 fillSudoku를 실행해 최종 answer 배열을 리턴한다.

 

왜 bool형을 쓰는거지..... 싶었는데 채울 수 있으면 재호출해서 다음을 채우고, 채울 수 없으면 비우고 다음으로 넘어간다는 것을 이용하기 위해서인 듯하다

로직 떠올려내는 것이 어렵다... 잘 알아두도록 하자