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

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

코드를 짜기가 굉장히 막막했는데 어떻게든 코드를 짜보려고 했다. 개인적으로 재귀가 너무 어려워서 아직도 원리에 대해 제대로 이해하지 못하고 있는 것 같다.

처음에 check 함수와 sudoku 함수 두개를 만들어서 각각의 셀에 대해 check하고 false를 리턴하지 않는다면 그 셀에 값을 넣는 방식으로 하면 될것 같았다.

import sys

def check(row, col, num):
    # 행 검사
    for i in range(9):
        if arr[row][i] == num:
            return False   
    # 열 검사
    for i in range(9):
        if arr[i][col] == num:
            return False 
    # 한칸 검사
    r, c = 3 * (row // 3), 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if arr[r + i][c + j] == num:
                return False
    return True

def sudoku():
    global arr
    row, col = -1, -1
    # 비어있는 셀 찾기
    for i in range(9):
        for j in range(9):
            if arr[i][j] == 0:
                row, col = i, j
                break
    # 더 이상 비어있는 셀이 없으면 종료한다.
    if row == -1 and col == -1:
        return True

    for num in range(1, 9+1):
        if check(row, col, num):
            arr[row][col] = num
            if sudoku():
                return True
            arr[row][col] = 0
    return False

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

sudoku()
for row in arr:
    print(" ".join(map(str, row)))

각각의 행, 열, 3x3 박스에 대해 1에서 9까지의 수를 검사해야 한다. check 함수로 검사한 후 해당 숫자가 유효하면 배열에 넣는다. 재귀를 반복하다가 모든 셀을 검사하게 되면 True를 리턴하고 종료한다.

시간초과가 나길래 계속 코드를 조금씩 바꿔가며 시도해봤는데 80퍼 즈음에서 계속 멈췄다. 원리는 아는데 시간을 줄일 방법을 도저히 알수가 없어서 너무 답답했다.

근데 허무하게도 코드를 C++로 바꿔서 내니까 바로 통과했다. 속도가 훨씬 빠르니 당연한건가 싶다가도 되게 허무했다.. 효율적인 코드를 짜기란 굉장히 어려운 일이라는 걸 계속 느끼는것 같다.

소스코드

---

#include <iostream>

using namespace std;

int arr[9][9] = { 0, };

bool check(int row, int col, int num) {
    // 행 검사
    for (int i = 0; i < 9; i++)
        if (arr[row][i] == num)
            return false;
    // 열 검사
    for (int i = 0; i < 9; i++)
        if (arr[i][col] == num)
            return false;
    // 한칸 검사
    int r = 3 * (row / 3);
    int c = 3 * (col / 3);
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (arr[r + i][c + j] == num)
                return false;
    return true;
}

bool sudoku() {
    int row = -1, col = -1;
    // 비어있는 셀 찾기
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++)
            if (arr[i][j] == 0) {
                row = i;
                col = j;
                break;
            }
        if (row != -1)
            break;
    }
    // 더 이상 비어있는 셀이 없으면 종료한다.
    if (row == -1 && col == -1)
        return true;

    for (int num = 1; num <= 9; num++)
        if (check(row, col, num)) {
            arr[row][col] = num;
            if (sudoku())
                return true;
            arr[row][col] = 0;
        }
    return false;
}

int main() {
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            cin >> arr[i][j];
    sudoku();
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++)
            cout << arr[i][j] << " ";
        cout << endl;
    }
}