백준 알고리즘 2580 (스도쿠) - C++, Python

[문제] 백준 알고리즘 2580 (스도쿠)

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

2580번: 스도쿠

빈 자리(숫자 0)에 스도쿠를 채우는 문제이다. 여러 경우가 존재한다면 하나만 출력한다.

DFS에서의 백트래킹을 이용한 문제이다.

 

[문제 해결]

1. 맵에서 0인 지점을 체크하면서, 0이 없으면 그대로 출력하고, 있으면 지점(y,x)을 return

    - 출력 시 여러 경우는 없어야하므로, exit(0)로 강제 종료한다. 이것 때문에 몇 번을 틀렸다.)

2. 지점(y,x)에 1~9까지 수를 대입해보며 가로 / 세로 / 사각형에 이미 그 수가 있는지 체크한다.

    - i = 0~8의 idx를 의미한다면, (y,x)에서 가로는 (i,x)인 경우, 세로는 (y,i)인 경우

    - 사각형은 ((y//3*3) + i//3, (x//3)*3 + i%3)인 경우

3. 이미 그 수가 없다면, 지점(y,x)에 대입하고 재귀시킨다.

4. 다음 재귀가 진행되지 않을 경우를 위해 백트래킹한다.

    - 지점(y,x)에 다시 0을 대입

 

[C++]

#include <cstdio>
#include <cstring> // memset
#include <cstdlib> // exit
using namespace std;
int map[9][9], n=0;

struct tuple {
	int i, j;
};

bool go(int y, int x, int num) { // 없는 숫자인가?
	for (int i = 0; i < 9; i++) {
		// 가로 또는 세로 확인
		if (map[i][x] == num || map[y][i] == num) return false;
		// 사각형 확인
		int sqy = int(y / 3) * 3 + int(i / 3);
		int sqx = int(x / 3) * 3 + i % 3;
		if (map[sqy][sqx] == num) return false;
	}
	return true;
}

tuple check_0() {
	tuple t;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (!map[i][j]) { // 0이면
				t.i = i, t.j = j;
				return t; // idx return
			}
		}
	}
	t.i = -1, t.j = -1;
	return t; // 0 없으면 초기값 -1
}

void solve_dfs(int depth) {
	if (depth == n) {  // 0이 존재하지 않을 때 출력
		// 여기서 출력하지 않으면 0으로 다시 백트래킹 주의
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				printf("%d ", map[i][j]);
			}
			printf("\n");
		}
		exit(0); // 강제종료 (안하면 틀림)
	}
	tuple t = check_0(); // 0의 idx(i, j), 없으면 -1 
	for (int i = 1; i <= 9; i++) { // 1~9 숫자
		if (go(t.i, t.j, i)) { // 없는 숫자이면
			map[t.i][t.j] = i; // 숫자 대입
			solve_dfs(depth+1); // 깊이+1
			map[t.i][t.j] = 0; // 백트래킹
		}
	}
}

int main() {
	memset(map, 0, sizeof(map));
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			scanf("%d", &map[i][j]);
			if (!map[i][j]) n++;
		}
	}
	solve_dfs(0);
	return 0;
}

 

[Python] (Pypy3로 제출해야 시간초과 x)

import sys
board = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]

def check():
    for i in range(9):
        for j in range(9):
            if not board[i][j]:
                return False, i, j
    return True, -1, -1

def go(y, x, n):
    for i in range(9):
        if board[i][x] == n or board[y][i] == n:
            return False
        sy = (y // 3) * 3 + i // 3
        sx = (x // 3) * 3 + i % 3
        if board[sy][sx] == n:
            return False
    return True

def print_board():
    for i in range(9):
        for j in range(9):
            print(board[i][j], end=' ')
        print()

def solve_dfs():
    flag, y, x = check()
    if flag:
        print_board()
        exit(0)
    for i in range(1, 10):
        if go(y, x, i):
            board[y][x] = i
            solve_dfs()
            board[y][x] = 0

solve_dfs()