[BOJ/백준] 2580 스도쿠

● [문제번호 2580] 스도쿠

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

2580번: 스도쿠

 

 

● 알아야 할 것

: DFS

: 재귀

: vector 자료구조와 메소드

: pair 자료구조와 메소드

 

 

● 풀이 과정

: 처음에 스도쿠 원리에 따라 잘 구현하였으나 '시간 초과'

그 다음에 또 어찌 구현하였으나 반례에서 걸려서 구글링을 했다.

 

: 빈 칸의 위치를 모두 저장해둔 상태에서

1. 만약 스도쿠를 다 채웠다면 STOP

 

2. 현재 빈칸에 1~9 차례로 대입

 

3. 사용가능한 숫자이면 다음 빈칸으로 재귀

3-1. 사용불가능하면 현재 빈칸에 다음 숫자 대입

 

: 반례

(입력1)

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

 

(출력1)

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

 

(입력2)

0 2 0 9 0 5 0 0 0

5 9 0 0 3 0 2 0 0

7 0 0 6 0 2 0 0 5

0 0 9 3 5 0 4 6 0

0 5 4 0 0 0 7 8 0

0 8 3 0 2 7 5 0 0

8 0 0 2 0 9 0 0 4

0 0 5 0 4 0 0 2 6

0 0 0 5 0 3 0 7 0

 

(출력2)

3 2 1 9 7 5 6 4 8
5 9 6 8 3 4 2 1 7
7 4 8 6 1 2 9 3 5
1 7 9 3 5 8 4 6 2
2 5 4 1 9 6 7 8 3
6 8 3 4 2 7 5 9 1
8 1 7 2 6 9 3 5 4
9 3 5 7 4 1 8 2 6
4 6 2 5 8 3 1 7 9

 

 

● 주의 할 것

: 스도쿠 조건 중 3X3 box에서 사용된 숫자를 찾아낼 때 주의한다.

int row = ROW / 3;

int col = COL / 3;

 

for(int r = row * 3; r < row * 3 + 3; r++) {

  for(int c = col * 3; c < col * 3 + 3; c++) {...}

}

 

 

● 참고 할 것

: 풀이과정 및 반례 참고

https://cryptosalamander.tistory.com/59

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// v : 빈 칸의 위치를 저장
// sudoku : 스도쿠 숫자 저장
// stop : 스도쿠를 다 채웠는 지 확인하는 신호
vector<pair<int, int>> v;
int sudoku[10][10];
bool stop = false;

// 해당 위치의 숫자가 가능한지 판단
bool check(int R, int C)
{
    // (R, C)위치 기준
    // 행과 열 중에 사용된 숫자가 있는 가
    for(int i = 0; i < 9; i++)
    {
        if(sudoku[R][C] == sudoku[R][i] && i != C)
            return false;
        else if(sudoku[R][C] == sudoku[i][C] && i != R)
            return false;
    }
    
    // (R, C)위치 기준
    // 3X3 box 시작위치
    int boxR = R / 3;
    int boxC = C / 3;
    
    // 3X3 box에서 사용된 숫자가 있는 가
    for(int r = boxR * 3; r < boxR * 3 + 3; r++)
        for(int c = boxC * 3; c < boxC * 3 + 3; c++)
            // (R, C)위치와 동일한가
            if(r == R && c == C)
                continue;
            else if(sudoku[r][c] == sudoku[R][C])
                return false;
    
    // 사용가능한 숫자인 경우
    return true;
}

// index : 채운 빈 칸의 수
void dfs(int index)
{
    // 스도쿠를 다 채운 경우
    if(index == v.size())
    {
        stop = true;
        return ;
    }
    
    int row = v[index].first;
    int col = v[index].second;
    
    // 1~9까지 대입해보기
    for(int i = 1; i <= 9; i++)
    {
        sudoku[row][col] = i;
        
        // 사용가능한 숫자인지 확인
        if(check(row, col))
            // 사용가능하면 다음 빈칸으로 이동
            dfs(index + 1);
        
        // 다 채웠다는 신호
        if(stop)
            return ;
    }
    
    // 빈칸에 대입가능한 숫자가 없는 경우 원상태로 돌리기
    sudoku[row][col] = 0;
    
    return ;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 스도쿠 입력
    for(int r = 0; r < 9; r++)
    {
        for(int c = 0; c < 9; c++)
        {
            cin >> sudoku[r][c];
            
            // 빈칸 위치 저장
            if(sudoku[r][c] == 0)
                v.push_back(pair<int, int>(r, c));
        }
    }
    
    // 재귀 시작
    dfs(0);
    
    // 스도쿠 출력
    for(int r = 0; r < 9; r++)
    {
        for(int c = 0; c < 9; c++)
            cout << sudoku[r][c] << " ";
        cout << "\n";
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [531 - 브루트 포스 - 재귀 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	6603	로또	https://pirateturtle.tistory.com/301
2	1182	부분수열의 합	https://pirateturtle.tistory.com/302
3	14225	부분수열의 합	https://pirateturtle.tistory.com/303
4	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/304
5	15658	연산자 끼워넣기 (2)	https://pirateturtle.tistory.com/305
6	14500	테트로미노	https://pirateturtle.tistory.com/306
7	16197	두 동전	https://pirateturtle.tistory.com/307
8	16198	에너지 모으기	https://pirateturtle.tistory.com/308
9	9663	N-Queen	https://pirateturtle.tistory.com/309
10	2580	스도쿠	https://pirateturtle.tistory.com/310
11	4574	스도미노쿠	https://pirateturtle.tistory.com/311
12	1987	알파벳	https://pirateturtle.tistory.com/312