[Baekjoon Online Judge] 백준 2580번 스도쿠(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2580번 스도쿠

(C++, Python)

(글쓴날 : 2020.04.10)

 

---

* Baekjoon Online Judge, 백준 2580번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2580번 스도쿠

---

1) 문제

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

2580번: 스도쿠

---

2) 풀이 과정

유명한 수학 퍼즐이자 게임인 스도쿠의 해를 구하는 프로그램을 작성하는 문제입니다.

스도쿠의 규칙은 가로, 세로, 3 X 3 크기의 정사각형 안에서 1~9사이의 숫자를 겹치지 않게 하여 모든 칸에 숫자를 채우는 것입니다.

문제에서 빈칸을 뜻하는 0과 숫자들로 채워져 있는 스도쿠판이 주어지며, 규칙에 맞추어 모든 빈칸에 알맞은 숫자를 기입한 뒤 출력해야 합니다.

단, 해가 여러 개일 경우 하나의 해만 출력하므로 각 언의 강제 종료 함수를 사용하면 되겠습니다.

 

저의 경우, DFS와 백트래킹을 적용하여 문제에 접근하였으며, C++과 Python을 사용했습니다.

처음 스도쿠판을 입력받을 때 빈칸인 0이 들어올 때마다 해당 인덱스를 zeroList에 저장하였고, 차후 깊이 우선 탐색을 할 때, 탐색 깊이와 zeroList의 크기를 비교하여 만약 같다면 모든 빈칸을 채운 것이므로 스도쿠판을 출력하고 종료하는 조건으로 설정했습니다.

또한, 탐색을 할 때 틀린 답으로는 더 이상 탐색하지 않도록 가로, 세로, 3 X 3 크기의 정사각형 안에 겹치는 숫자가 있을 시 회귀하는 check() 함수를 만들어 백트래킹을 구현해 문제를 해결하였습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <utility>
#include <vector>
 
using namespace std;
 
int sudoku[9][9];
vector<pair<int, int>> zeroList;
 
bool check(int k, int sudoku[][9], int x, int y)
{
    for (int i = 0; i < 9; i++)
    {
        if (sudoku[x][i] == k)
            return false;
    }
    for (int i = 0; i < 9; i++)
    {
        if (sudoku[i][y] == k)
            return false;
    }
 
    int ii = (x / 3) * 3;
    int jj = (y / 3) * 3;
 
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (sudoku[ii + i][jj + j] == k)
                return false;
        }
    }
    return true;
}
 
void DFS(int depth)
{
    if (depth == zeroList.size())
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                cout << sudoku[i][j] << " ";
            }
            cout << "\n";
        }
        exit(0);
    }
 
    int x = 0;
    int y = 0;
 
    for (int k = 1; k <= 9; k++)
    {
        x = zeroList[depth].first;
        y = zeroList[depth].second;
 
        if (check(k, sudoku, x, y))
        {
            sudoku[x][y] = k;
            DFS(depth + 1);
            sudoku[x][y] = 0;
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> sudoku[i][j];
 
            if (!sudoku[i][j])
                zeroList.push_back({i, j});
        }
    }
 
    DFS(0);
 
    return 0;
}

---

* Python 코드(PyPy3)

import sys
input = sys.stdin.readline
 
 
def check(k, x, y):
    if k in sudoku[x]:
        return False
 
    # zip() 쓰면 시간 초과
    # if k in list(zip(*sudoku))[y]:
    #     return False
    for i in range(9):
        if sudoku[i][y] == k:
            return False
    
    ii, jj = (x // 3) * 3, (y // 3) * 3
 
    for i in range(3):
        for j in range(3):
            if sudoku[ii + i][jj + j] == k:
                return False
 
    return True
    
 
def DFS(depth):
    if depth == len(zeroList):    
        for line in sudoku:
            print(*line)
        sys.exit(0)
    
    for k in range(1, 10):
        x = zeroList[depth][0]
        y = zeroList[depth][1]
        
        if check(k, x, y):
            sudoku[x][y] = k
            DFS(depth + 1)
            sudoku[x][y] = 0
 
 
sudoku = [list(map(int, input().split())) for _ in range(9)]
zeroList = [(i, j) for j in range(9) for i in range(9) if sudoku[i][j] == 0]
 
DFS(0)

---