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

백준 온라인 저지(BOJ) 2580번 스도쿠
https://www.acmicpc.net/problem/2580

2580번: 스도쿠

* 사용언어 : C언어, C++
 

1. 문제

9 * 9 크기의 스도쿠를 풀고 출력 (빈 칸은 0으로 주어짐)

 

2. 풀이

1) 설계

다른 백트래킹 유형의 문제들과 마찬가지로 DFS를 기반으로 구현했습니다.
풀이의 핵심인 재귀 함수(sudoku)의 내부 구조는 아래와 같습니다.
 

• 모든 숫자를 채운 경우 (depth == 81)
  • 정답 출력 후 종료
• 모든 숫자를 채우지 못한 경우
  • 해당 depth에서 확인할 칸의 y, x 확인 (y = depth / 9, x = depth % 9)
    • map[y][x]가 0이 아닌 경우
      • 다음 depth로 이동 (이미 숫자가 채워져있으므로)
    • map[y][x]가 0인 경우
      • 1부터 9까지 순회하면서 row, col, square를 모두 확인 후 가능한 숫자를 map[y][x]에 입력
      • 다음 depth로 이동 (가능한 숫자를 채웠으므로)
      • map[y][x]를 0으로 바꾸고 다음 숫자 진행 (DFS 반복)

 
위 설계대로 구현한 코드는 페이지 아래 쪽에 있으니 참고하시면 됩니다.
해당 함수 외의 내용은 소스 코드로 설명 대체하겠습니다.
 

2) 반례

다음은 풀이에 도움이 되는 유용한 반례들입니다.
 
저는 1%와 29%에서 틀렸습니다 가 나왔었는데,
질문 게시판을 통해 아래 반례를 찾아 디버깅한 후 정답을 맞출 수 있었습니다.
 
[1% 오답 반례 (정답 못 찾음)]
0 0 0 0 4 3 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 5 0 0 0 0
0 8 0 7 0 0 0 2 0
0 6 0 0 0 0 0 0 3
0 0 0 0 0 0 0 4 0
0 0 5 8 0 0 6 0 0
4 0 0 1 0 0 0 0 0
3 0 0 0 0 0 5 0 0

[29% 오답 반례 (2개의 정답(18줄)이 출력됨)]
0 0 0 0 0 0 0 0 0
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
0 0 0 0 0 0 0 0 0
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
0 0 0 0 0 0 0 0 0
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2580_스도쿠
1116KB	192ms
*/
#include <cstdio>

const int LM = 9;
int map[LM][LM], finished;

int rowCheck(int i, int ty) {
	for (int x = 0; x < LM; ++x) {
		if (map[ty][x] == i) {
			return 0;
		}
	}
	return 1;
}

int colCheck(int i, int tx) {
	for (int y = 0; y < LM; ++y) {
		if (map[y][tx] == i) {
			return 0;
		}
	}
	return 1;
}

int squareCheck(int i, int ty, int tx) {
	for (int y = 0; y < 3; ++y) {
		for (int x = 0; x < 3; ++x) {
			if (map[ty / 3 * 3 + y][tx / 3 * 3 + x] == i) {
				return 0;
			}
		}
	}
	return 1;
}

void sudoku(int depth) {
	if (depth == 81) {
		for (int y = 0; y < LM; ++y) {
			for (int x = 0; x < LM; ++x) {
				printf("%d ", map[y][x]);
			}
			printf("\n");
		}
		finished = 1;
		return;
	}

	int ty = depth / LM;
	int tx = depth % LM;

	if (map[ty][tx] != 0) sudoku(depth + 1);
	else {
		for (int i = 1; i <= LM; ++i) {
			if (rowCheck(i, ty) == 0) continue;
			if (colCheck(i, tx) == 0) continue;
			if (squareCheck(i, ty, tx) == 0) continue;

			map[ty][tx] = i;
			sudoku(depth + 1);
			if (finished) break;
			map[ty][tx] = 0;
		}
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	for (int y = 0; y < LM; ++y) {
		for (int x = 0; x < LM; ++x) {
			scanf("%d ", &map[y][x]);
		}
	}
	sudoku(0);
	return 0;
}