3주차(백트래킹) - [C++]백준2580 스도쿠

19 Mar 2022 in Study on Algorithm

백준2580 스도쿠 링크

문제

예제 입력

---

코드

#include <iostream>
#include <vector>
#define x first
#define y second
using namespace std;

bool find_sudoku = false;
vector<pair<int, int>> num;
vector<vector<int>> arr(9, vector<int>(9));

bool check(pair<int, int> p) {
	int row = p.x / 3;
	int col = p.y / 3;

    // row, col 확인
	for (int i = 0; i < 9; i++) {
		if (arr[i][p.y] == arr[p.x][p.y] && i != p.x)	return false;
		if (arr[p.x][i] == arr[p.x][p.y] && i != p.y)	return false;
	}
    // 3 x 3 확인
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (arr[(row * 3) + i][(col * 3) + j] == arr[p.x][p.y] && (row * 3) + i != p.x && (col * 3) + j != p.y)	return false;
		}
	}
	return true;
}

void sudoku(int n) {
    // 모든 빈칸이 다 채움
	if (n == num.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)	cout << arr[i][j] << " ";
			cout << "\n";
		}
        // exit(0); 프로그램 종료
		find_sudoku = true;
		return;
	}

    // 1~9 숫자를 넣음
	for (int i = 1; i <= 9; i++) {
		arr[num[n].x][num[n].y] = i;

		if (check(num[n]))	sudoku(n + 1);
		if (find_sudoku)	return;
	}
    // 이 숫자가 아니여서 되돌림
	arr[num[n].x][num[n].y] = 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];
            // 빈칸 따로 저장
			if (arr[i][j] == 0)	num.push_back({ i, j });
		}
	}
	sudoku(0);
}

설명

이 문제는 9 x 9 스도쿠판에서 비어있는 칸에 값을 찾아 스도쿠를 완성시키야 합니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 먼저 초기값을 입력받는데 그중 빈칸을 따로 배열에 저장했다가 스도쿠를 실행할때 빈칸만 찾아가서 시도를 해보는데 check()함수로 기본적인 스도쿠에 룰을 확인하며 채워나갑니다. 만약 도중에 더이상 완성이 안된다면 어디선가 잘못된 값을 넣은 것이니 되돌리고 다음 값을 넣어 계속 완성해 갑니다. 그리고 정답이 나오면 출력하고 나머지는 시도할 필요없어 종료됩니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과