1. 과제
백준 백트래킹 2580번 스도쿠 문제
2. 참고한 사항 / 중요 사항
개수를 알고 있고, 한 글자씩 잘라서 input을 받을 때
아래와 같이 반복문으로 진행하면서 한 글자씩 scanf("%1d",&a[i])을 하면 된다. %1d가 (정수)+(띄어쓰기1칸)이므로 이렇게 진행한다!
int a[7];
for(int i=0;i<7;i++){ //7개의 수를 받겠다.
scanf("%1d",&a[i]); //한글자씩 받아서 a배열에 넣기
}출처 : https://dbstndi6316.tistory.com/33
전체적인 풀이 원리
어떻게 풀어야 할지 감이 잘 안 오고 조금 어려워서, 다른 분의 원리를 참고하면서 해결해보려고 했으나 재귀함수로 풀어내는 게 어려워서 코드를 참고하면서 이해하는 방식으로 공부했다.
(아래에 문제 출처를 보니까 정보올림피아드 초등부, 중등부 문제였다는데 이렇게 어린 나이에 푸신 분들은 정말 대단한 분들인 것 같다.. 대학생도 어려운데...)
일단 먼저 resolve 함수는 입력을 받은 배열(sudoku)의 한 칸씩 살펴보면서 0인 칸들을 1부터 9까지 가능한 수들을 탐색하는 것이 주 업무이다. 이때 필요한 함수는 possibility 함수인데, 이 함수는 현재 이 칸과 같은 행,열,3*3칸을 다 보면서 이 칸에 들어갈 수 있는 값들을 판별하는 함수이다.
먼저 possibility 함수부터 보자면
행, 열, 값을 매개변수로 받아서 이 [행][열]에 이 값이 가능한지를 판단한다.
그래서 같은 행에 있는 원소들을 반복문으로 확인해보면서 value 값과 같은지를 확인하고, 같은 게 있다면 false를 리턴해서 이 값은 이 자리에 가능하지 않음을 구해준다.
이런 식으로 같은 열에 있는 원소들도 확인해보고,
// 같은 행에 있는 열 원소 중에 겹치는 수가 있는지
for (int i = 0; i < 9; i++) {
if (sudoku[row][i] == value)
return false;
}
// 같은 열에 있는 행 원소 중에 겹치는 수가 있는지
for (int i = 0; i < 9; i++) {
if (sudoku[i][col] == value)
return false;
}다음으로 33 칸을 살펴봐야 하는데 이 부분은 이 행의 첫 위치를 (row/3)x3 으로 구하는 식으로 첫 칸의 행/열 위치를 구할 수 있다. 그리고 이 첫 위치부터 마지막 9번째 위치까지,
시작 위치와 같은 행 3칸 시작 위치와 같은 열 3칸을 반복문으로 돌면서 value값과 같은지 확인한다.
// 같은 3*3 칸 안에 있는 원소 중에 겹치는 수가 있는지
int start_row = (row / 3) * 3; // value가 속한 3*3의 행의 첫 위치
int start_col = (col / 3) * 3; // value가 속한 3*3의 열의 첫 위치
for (int i = start_row; i < start_row + 3; i++) {
for (int j = start_col; j < start_col + 3; j++) {
if (sudoku[i][j] == value)
return false;
}
}이 3개의 검사를 모두 통과한 것은 이 value가 이 칸에 들어갈 가능성이 있다는 뜻이므로, 이 이후에 true를 리턴하면서 이 value가 가능할 수 있다는 것을 알려준다!
- possibility 함수
bool possibility(int row, int col, int value) {
// 같은 행에 있는 열 원소 중에 겹치는 수가 있는지
for (int i = 0; i < 9; i++) {
if (sudoku[row][i] == value)
return false;
}
// 같은 열에 있는 행 원소 중에 겹치는 수가 있는지
for (int i = 0; i < 9; i++) {
if (sudoku[i][col] == value)
return false;
}
// 같은 3*3 칸 안에 있는 원소 중에 겹치는 수가 있는지
int start_row = (row / 3) * 3; // value가 속한 3*3의 행의 첫 위치
int start_col = (col / 3) * 3; // value가 속한 3*3의 열의 첫 위치
for (int i = start_row; i < start_row + 3; i++) {
for (int j = start_col; j < start_col + 3; j++) {
if (sudoku[i][j] == value)
return false;
}
}
return true; // 중복되는 것이 없을 경우 true 반환
}다시 돌아와서, resolve 함수는 이렇게 possibility 함수에서 가능 여부를 따진 것을 바탕으로, 재귀적으로 다음 칸을 불러오는 방식으로 계속 진행해나가는 백트래킹 방식을 적용한다.
만약 sudoku[row][col]위치의 값이 0이라면, 1부터 9까지의 value를 다 넣어보면서 possiblity 함수를 통해 중복되는 값인지를 판단하고, 중복되는 값이 아니라면 해당 위치의 값을 value로 대입한 후 재귀로 다음 칸을 진행한다.(resolve(row, col + 1))
마지막 (8,8)칸까지 간 경우에는 출력되고 exit(0)으로 처리해서 이 프로세스가 아예 끝나도록 했는데, 만약 마지막까지 가지 못해 exit(0)을 만나지 못한 경우에는 재귀를 마치고 원래 함수로 돌아오게 된다. 그러면 이 value 값은 이 위치가 아니라는 뜻이니까, 해당 위치의 값을 다시 0으로 초기화해야 한다!!
// 만약 해당 위치의 값이 0이라면 1~9까지 중 가능한 수 탐색
if (sudoku[row][col] == 0) {
for (int value = 1; value <= 9; value++) {
// value 값이 중복되지 않는지 검사
if (possibility(row, col, value)) {
sudoku[row][col] = value;
resolve(row, col + 1); // 다음 칸 진행
}
}
sudoku[row][col] = 0; // 채워지는 도중에 더이상 채울 수 없는 상태일 경우에, 다시 되돌아와서 그 자리를 0으로 초기화함
return;
}
resolve(row, col + 1);- resolve 함수
void resolve(int row, int col) {
// 해당 행이 다 채워졌을 경우 다음 행의 첫 번째 열부터 시작
if (col == 9) {
resolve(row + 1, 0);
return;
}
// 행과 열이 모두 채워졌을 경우 출력 후 종료
if (row == 9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
printf("%d ", sudoku[i][j]);
}
printf("\n");
}
exit(0);
}
// 만약 해당 위치의 값이 0이라면 1~9까지 중 가능한 수 탐색
if (sudoku[row][col] == 0) {
for (int value = 1; value <= 9; value++) {
// value 값이 중복되지 않는지 검사
if (posibility(row, col, value)) {
sudoku[row][col] = value;
resolve(row, col + 1); // 다음 칸 진행
}
}
sudoku[row][col] = 0; // 채워지는 도중에 더이상 채울 수 없는 상태일 경우에, 다시 되돌아와서 그 자리를 0으로 초기화함
return;
}
resolve(row, col + 1);
}+) exit() 함수를 쓴 이유?
(8,8)자리까지 간 후 return으로 처리를 하게 된다면 다시 상위 함수로 되돌아가게 된다. 이를 방지하기 위해 행과 열이 모두 채워지면 바로 스도쿠를 출력하고 프로그램을 종료시키는 방식으로 진행한 것이다.
원리 및 코드 출처 : https://st-lab.tistory.com/119 (자바 코드)
3. 전체 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int sudoku[9][9];
bool posibility(int row, int col, int value) {
// 같은 행에 있는 열 원소 중에 겹치는 수가 있는지
for (int i = 0; i < 9; i++) {
if (sudoku[row][i] == value)
return false;
}
// 같은 열에 있는 행 원소 중에 겹치는 수가 있는지
for (int i = 0; i < 9; i++) {
if (sudoku[i][col] == value)
return false;
}
// 같은 3*3 칸 안에 있는 원소 중에 겹치는 수가 있는지
int start_row = (row / 3) * 3; // value가 속한 3*3의 행의 첫 위치
int start_col = (col / 3) * 3; // value가 속한 3*3의 열의 첫 위치
for (int i = start_row; i < start_row + 3; i++) {
for (int j = start_col; j < start_col + 3; j++) {
if (sudoku[i][j] == value)
return false;
}
}
return true; // 중복되는 것이 없을 경우 true 반환
}
void resolve(int row, int col) {
// 해당 행이 다 채워졌을 경우 다음 행의 첫 번째 열부터 시작
if (col == 9) {
resolve(row + 1, 0);
return;
}
// 행과 열이 모두 채워졌을 경우 출력 후 종료
if (row == 9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
printf("%d ", sudoku[i][j]);
}
printf("\n");
}
exit(0);
}
// 만약 해당 위치의 값이 0이라면 1~9까지 중 가능한 수 탐색
if (sudoku[row][col] == 0) {
for (int value = 1; value <= 9; value++) {
// value 값이 중복되지 않는지 검사
if (posibility(row, col, value)) {
sudoku[row][col] = value;
resolve(row, col + 1); // 다음 칸 진행
}
}
sudoku[row][col] = 0; // 채워지는 도중에 더이상 채울 수 없는 상태일 경우에, 다시 되돌아와서 그 자리를 0으로 초기화함
return;
}
resolve(row, col + 1);
}
int main() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
scanf("%1d", &sudoku[i][j]);
}
}
resolve(0, 0);
return 0;
}4. 제출 화면
