[BOJ/백준 2580][C++] 스도쿠

문제

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

백준 2580

백준 2580

백준 2580

 

문제 내용

완성되지 않은 9*9 크기의 스도쿠를 입력받아 완성시키는 문제이다.

 

문제 풀이

이 문제는 백트래킹 방식을 통해 문제를 풀었다.

아직 채우지 못한 빈칸을 찾아서 배열에 저장한 뒤, 그 빈칸에 1~9를 차례로 넣어보며 스도쿠를 완성시키는 방식으로 문제를 해결하면 된다.

스도쿠의 특성상, 같은 행 / 같은 열 / 같은 3*3칸 안에서는 1~9이 숫자가 한 번씩만 나올 수 있다.

이 특성을 체크하기 위해 check() 함수를 별도로 만들어 사용했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<pair<int, int>>blank;
bool finish = false;

//1~9 체크
bool check(int a, int b, vector<vector<int>>& sudoku) {
	//한줄 체크
	for (int i = 0; i < 9; i++) { 
		if (sudoku[i][b] == sudoku[a][b] && i != a) return false; //행 확인
		if (sudoku[a][i] == sudoku[a][b] && i != b) return false; //열 확인
	}

	//3*3확인
	int sa = (a / 3) * 3;
	int sb = (b / 3) * 3;
	for (int i = sa; i < sa + 3; i++) {
		for (int j = sb; j < sb + 3; j++) {
			if (i == a && j == b) continue;
			if (sudoku[i][j] == sudoku[a][b]) return false; //겹치는거 존재
		}
	}

	//겹치는게 없다면 true반환
	return true;
}

//backtracking 함수
void backtracking(int n, vector<vector<int>>& sudoku) {
	if (n == blank.size()) { //모든 칸 다 채움
		finish = true;
		return;
	}

	//n번째 빈칸 좌표
	int a = blank[n].first;
	int b = blank[n].second;

	for (int i = 1; i <= 9; i++) {
		sudoku[a][b] = i; //1~9넣어보기
		if (check(a, b, sudoku)) {
			backtracking(n + 1, sudoku);
		};
		
		if (finish) return; //스도쿠 완성 => 계속 리턴
	}

	sudoku[a][b] = 0; //못채우면 되돌리기
	return;
}

//solution함수
vector<vector<int>> solution(vector<vector<int>> sudoku) {
	//blank에 빈 공간 저장
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
			if (sudoku[i][j] == 0)
				blank.push_back(make_pair(i, j));


	backtracking(0,sudoku);
	return sudoku;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	//입력
	vector<vector<int>>sudoku(9, vector<int>(9));
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
			cin >> sudoku[i][j];

	//문제 해결
	auto output= solution(sudoku);
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << output[i][j] << ' ';
		}cout << '\n';
	}
	return 0;
}

 

문제 코드 설명

이 문제는 프로그래머스의 solution() 함수를 만들어 푸는 방식으로 진행했다.

그렇기 때문에 입력과 출력은 이미 작성되어 있었다.

(백준에서 바로 풀 때는 입출력 또한 완성시켜야 한다.)

 

1) solution() 함수

스도쿠 배열에서 빈칸인 부분(값이 0인 곳)을 모두 찾아 black 배열에 pair로 묶어서 넣어둔다.

이후 backtracking() 함수에서 사용한다.

 

2) backtracking() 함수

일단 재귀 함수의 종료 조건을 작성해주었다.

더 이상 채워야 할 빈칸이 남아있지 않다면 종료해야 하기 때문에, finish를 ture로 만들었다.

 

backtracking 함수 안에서, 차례로 blank의 위치를 파악해서 그 자리에 1~9까지의 수를 넣어본다.

이후 check함수로 그 위치에 1~9를 넣었을 때 스도쿠의 조건에 어긋나지 않는지 파악한다.

어긋나지 않는다면 그대로 다음 빈칸을 채우기 위해 backtracking 함수를 다시 부른다.

만약 어긋난다면 그 빈칸의 자리를 다시 0으로 되돌리고 반환하면 된다.

 

3) check() 함수

같은 열/같은 행에서 겹치는 것이 있는지 확인한다.

이후 3*3칸 안에서 겹치는 것이 있는지 확인한다.

만약 겹치는 것이 존재한다면 false를, 그렇지 않다면 true를 반환한다.