[BOJ/백준] 4574 스도미노쿠

● [문제번호 4574] 스도미노쿠

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

4574번: 스도미노쿠

 

● 알아야 할 것

: DFS

: 재귀

: 2580 스도쿠 문제

 

 

● 풀이 과정

: 처음에 문제를 이해가 안되어서 구글링을 통해 이해되었다.

2580 스도쿠 문제와 비슷하지만 조금 더 신경써야하는 문제였다.

 

: 도미노 타일이라는 제약때문에

숫자를 1개씩 대입이 아닌 숫자를 2개씩 SET으로 대입해야한다.

 

또한 빈 칸을 찾아가는 순서를 고려하였을 때,

도미노 타일이 놓아질 수 있는 경우의 수는 2가지이다.

왜냐하면 빈 칸을 찾은 위치 기준으로 왼쪽과 위쪽은 이미 채워진 숫자이기 때문이다.

 

도미노 타일 놓는 2가지 경우의 수 이해하기!

1. 스도쿠 보드판에서 빈 칸을 찾는다.

2. 사용하지 않은 도미노 타일을 찾는다.

3. 일단 도미노 타일 체크인

4. 가로 방향으로 놓아보고 / 숫자 위치 바꿔보고 / 세로 방향으로 놓아보고 / 숫자 위치 바꿔보고

5. 문제 없다면 다시 1로 재귀

6. 문제가 된다면 도미노 타일 체크아웃하고 2번으로 반복문

7. 1~6번을 재귀와 반복문을 이용하여 스도쿠를 채운다.

 

 

● 주의 할 것

: 처음에 빈 칸의 위치를 모두 기억해서 하려고 하였으나

타일이라는 제약사항때문에 오히려 더 복잡해진다.

 

 

● 참고 할 것

: 풀이과정 참고

https://velog.io/@lacram/C-%EB%B0%B1%EC%A4%80-4574%EB%B2%88-%EC%8A%A4%EB%8F%84%EB%AF%B8%EB%85%B8%EC%BF%A0

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// used : 사용된 도미노 타일 기록
// sudoku : 스도쿠 숫자 저장
// stop : 스도쿠를 다 채웠는 지 확인하는 신호
bool used[10][10];
int sudoku[10][10];
bool stop = false;
int N;

// 해당 위치의 숫자가 가능한지 판단
// (2580 스도쿠 문제와 동일하게 사용)
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;
}

// 1칸 씩 재귀형태로 채워나감
void dfs()
{
    // 다 채웠다는 신호 ON
    if(stop)
        return ;
    
    // 스도쿠에서 0인 숫자 찾기
    int row = -1, col = -1;
    
    for(int r = 0; r < 9; r++)
    {
        for(int c = 0; c < 9; c++)
        {
            if(sudoku[r][c] == 0)
            {
                row = r;
                col = c;
                break;
            }
        }
        if(row != -1)
            break;
    }
    
    // 스도쿠에서 0인 숫자가 없는 경우
    // 즉, 다 채운 경우
    if(row == -1)
    {
        stop = true;
        
        // 스도쿠 출력
        for(int r = 0; r < 9; r++)
        {
            for(int c = 0; c < 9; c++)
                cout << sudoku[r][c];
            cout << "\n";
        }
        
        return ;
    }
    
    // 도미노 타일 하나씩 대입해보기
    for(int set1 = 1; set1 < 9; set1++)
    {
        for(int set2 = set1 + 1; set2 < 10; set2++)
        {
            // 사용 안한 도미노 타일 발견한 경우
            if(!used[set1][set2])
            {
                // 도미노 타일 사용 체크인
                used[set1][set2] = true;
                used[set2][set1] = true;
                
                // 가로 방향
                // (row, col) , (row, col + 1)
                if(col + 1 < 9 && sudoku[row][col + 1] == 0)
                {
                    sudoku[row][col] = set1;
                    sudoku[row][col + 1] = set2;
                    if(check(row, col) && check(row, col + 1))
                        dfs();
                    sudoku[row][col] = 0;
                    sudoku[row][col + 1] = 0;
                }
                // 가로방향 (도미노 숫자 위치 바꿔서)
                if(col + 1 < 9 && sudoku[row][col + 1] == 0)
                {
                    sudoku[row][col] = set2;
                    sudoku[row][col + 1] = set1;
                    if(check(row, col) && check(row, col + 1))
                        dfs();
                    sudoku[row][col] = 0;
                    sudoku[row][col + 1] = 0;
                }
                
                // 세로 방향
                // (row, col) , (row + 1, col)
                if(row + 1 < 9 && sudoku[row + 1][col] == 0)
                {
                    sudoku[row][col] = set1;
                    sudoku[row + 1][col] = set2;
                    if(check(row, col) && check(row + 1, col))
                        dfs();
                    sudoku[row][col] = 0;
                    sudoku[row + 1][col] = 0;
                }
                // 세로방향 (도미노 숫자 위치 바꿔서)
                if(row + 1 < 9 && sudoku[row + 1][col] == 0)
                {
                    sudoku[row][col] = set2;
                    sudoku[row + 1][col] = set1;
                    if(check(row, col) && check(row + 1, col))
                        dfs();
                    sudoku[row][col] = 0;
                    sudoku[row + 1][col] = 0;
                }
                
                // 도미노 타일 사용 체크아웃
                used[set1][set2] = false;
                used[set2][set1] = false;
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 몇 개의 puzzle 인지 갯수 세기
    int puzzle = 1;
    while(true)
    {
        // 도미노의 개수
        cin >> N;
        if(N == 0)
            break;
        
        // 도미노 타일을 기억해야하므로
        // 한 줄씩 기억
        int num[2];
        string rowcol;
        for(int n = 0; n < N; n++)
        {
            for(int i = 0; i < 2; i++)
            {
                cin >> num[i] >> rowcol;
                
                int r = rowcol[0] - 'A';
                int c = rowcol[1] - '1';
                
                sudoku[r][c] = num[i];
            }
            // 도미노 타일 사용 체크
            used[num[0]][num[1]] = true;
            used[num[1]][num[0]] = true;
        }
        
        // 1~9 숫자의 위치 기록
        for(int i = 1; i <= 9; i++)
        {
            cin >> rowcol;
            int r = rowcol[0] - 'A';
            int c = rowcol[1] - '1';
            
            sudoku[r][c] = i;
        }
        
        // 출력
        cout << "Puzzle " << puzzle << "\n";
        dfs();
        
        // 다음 퍼즐을 위해 초기화 작업
        puzzle++;
        stop = false;
        fill(&sudoku[0][0], &sudoku[10][10], 0);
        fill(&used[0][0], &used[10][10], false);
    }
    
    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