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

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

2580번: 스도쿠

---

문제

---

문제 풀이

우선 스도쿠의 규칙에 따르면 체크해야 할 조건이 두 가지가 있다.

1. 같은 행, 열에 같은 숫자가 존재하면 안된다.
2. 속해있는 3x3 정사각형 안에 같은 숫자가 존재하면 안된다.

 

C++ 상세 풀이

다양한 풀이가 있겠지만 나는 백트래킹 방법, 그 중에서도 9 x 9칸을 해결할 때까지 순회하는 방법을 사용했다.

 

for (int i = 0; i < 9; ++i)
    for (int j = 0; j < 9; ++j) {
        std::cin >> arr[i][j];

        if (arr[i][j] == 0)
            cnt++;
    }

행렬을 입력받을 때, 만약 0이라면 해결해야 하는 칸이므로 cnt 변수를 증가시켜준다. 후에 dfs 함수에서 쓰인다.

 

void dfs(int x, int y, int cur) {
    if (cur == cnt) // 해결이 완료되었으면 최종 출력
        print();
    else if (y == 9) // 다음 줄로 넘어감
        dfs(x + 1, 0, cur);
    
    if (arr[x][y] == 0) {
        for (int i = 1; i <= 9; ++i) {
            if (check(x, y, i)) {
                arr[x][y] = i;
                dfs(x, y + 1, cur + 1);
                arr[x][y] = 0; // 혹여라도 이후에 잘못되었으면 복구해야 함
            }
        }
    }
    else
        dfs(x, y + 1, cur);
}

dfs 함수의 인자로는 x, y, cur이 들어간다. x, y는 행렬의 x좌표/y좌표를 뜻하고, cur은 현재 스도쿠가 얼마나 해결되었는지를 말한다. 그래서 cur == cnt라면 모든 문제가 해결되었으므로 전체 행렬을 출력(print함수)하고 프로그램을 종료한다.

y가 9라면 다음 줄로 한 행을 모두 순회했다는 뜻이므로 다음 줄로 넘어가기 위해 x + 1, 0, cur을 인자로 준다. 

 

arr[x][y]가 0이라면 해결해야 하는 빈칸이라는 뜻이다. 1에서 9의 숫자 중 하나가 들어갈 수 있으므로 하나하나 들어갈 수 있는지 check함수에 넣어준다. 만약 가능하다면, arr[x][y]칸을 i로 채운 다음 다시 dfs로 들어간다. 여기서 빈칸이 해결되었으므로 cur + 1을 인자로 주게 된다.

 

arr[x][y] = 0을 주는 이유는 혹여라도 바로 전 줄에서 dfs에 들어갔는데 이후에 잘못된 부분이 있어 다시 돌아오게 되면 해결되지 않았으니 0으로 초기화해줘야 하기 때문이다.

 

bool check(int x, int y, int val) {
    // 같은 행, 열에 같은 숫자가 있으면 불가능
    for (int i = 0; i < 9; ++i) {
        if (arr[x][i] == val) return false;
        if (arr[i][y] == val) return false;
    }

    // 3 x 3 정사각형 범위를 위한 변수 선언
    int start_x = (x / 3) * 3;
    int end_x = (x / 3) * 3 + 3;
    int start_y = (y / 3) * 3;
    int end_y = (y / 3) * 3 + 3;

    // 3 x 3 정사각형 안에 같은 값이 있으면 불가능
    for (int i = start_x; i < end_x; ++i) {
        for (int j = start_y; j < end_y; ++j)
            if (arr[i][j] == val) 
                return false;
    }

    return true;
}

빈칸에 맞는 값이 들어갔는지 확인하기 위한 함수다. 주석을 달아놨으니 참고하면 좋을 것 같다.

Python 상세 풀이

두 가지 방법을 사용했다. C++에서와 동일하게 cnt 변수를 선언해 문제 해결을 카운트하는 방식, 아예 입력받을 때 0인 좌표를 따로 리스트로 저장해 활용하는 방법을 활용했다. 큰 결은 같다.

 

if __name__ == "__main__":
    cnt = 0

    arr = [0 for _ in range(9)]
    for i in range(9):
        arr[i] = list(map(int, input().split()))
        cnt = cnt + arr[i].count(0)

    dfs(0, 0, 0)

행렬을 입력받을 때, 만약 0이라면 해결해야 하는 칸이므로 cnt 변수를 증가시켜준다. 후에 dfs 함수에서 쓰인다.

 

def dfs(x, y, cur):
    if cur == cnt: # 해결이 완료되었으면 최종 출력
        print_all()
    elif y == 9: # 다음 줄로 넘어감
        dfs(x + 1, 0, cur)
    
    elif arr[x][y] == 0:
        for i in range(1, 10):
            if check(x, y, i):
                arr[x][y] = i
                dfs(x, y + 1, cur + 1)
                arr[x][y] = 0 # 혹여라도 이후에 잘못되었으면 복구해야 함
        
    else:
        dfs(x, y + 1, cur)

dfs 함수의 인자로는 x, y, cur이 들어간다. x, y는 행렬의 x좌표/y좌표를 뜻하고, cur은 현재 스도쿠가 얼마나 해결되었는지를 말한다. 그래서 cur == cnt라면 모든 문제가 해결되었으므로 전체 행렬을 출력(print함수)하고 프로그램을 종료한다.

y가 9라면 다음 줄로 한 행을 모두 순회했다는 뜻이므로 다음 줄로 넘어가기 위해 x + 1, 0, cur을 인자로 준다. 

 

arr[x][y]가 0이라면 해결해야 하는 빈칸이라는 뜻이다. 1에서 9의 숫자 중 하나가 들어갈 수 있으므로 하나하나 들어갈 수 있는지 check함수에 넣어준다. 만약 가능하다면, arr[x][y]칸을 i로 채운 다음 다시 dfs로 들어간다. 여기서 빈칸이 해결되었으므로 cur + 1을 인자로 주게 된다.

 

arr[x][y] = 0을 주는 이유는 혹여라도 바로 전 줄에서 dfs에 들어갔는데 이후에 잘못된 부분이 있어 다시 돌아오게 되면 해결되지 않았으니 0으로 초기화해줘야 하기 때문이다.

 

def check(x, y, cur):
    # 같은 행, 열에 같은 숫자가 있으면 불가능
    for i in range(9):
        if arr[x][i] == cur: return False
        if arr[i][y] == cur: return False

    # 3 x 3 정사각형 범위를 위한 변수 선언
    start_x = (x // 3) * 3
    end_x = (x // 3) * 3 + 3
    start_y = (y // 3) * 3
    end_y = (y // 3) * 3 + 3

    # 3 x 3 정사각형 안에 같은 값이 있으면 불가능
    for i in range(start_x, end_x):
        for j in range(start_y, end_y):
            if arr[i][j] == cur:
                return False

    return True

빈칸에 맞는 값이 들어갔는지 확인하기 위한 함수다. 주석을 달아놨으니 참고하면 좋을 것 같다.

 

코드 전문

C++

Python

소감

너무 어려웠던 문제다. 정답률이 27%이기도 하고 N-Queen과 같은 난이도로 책정되어 있던데 개인적으로 이 문제가 더 막막했다. 물론 아이디어가 떠오르고 나서는 빨리 풀렸던 것 같은데 이 문제도 다시 풀어봐야 할 것 같다.