백준 2580 스도쿠

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

2580번: 스도쿠

스도쿠 문제는 말 그대로 빈칸인 스도쿠를 주면 한개의 정답을 입력해서 출력해주라는 문제입니다.

문제를 봤을때 백트래킹을 이용해야한다 생각이 드는 문제였습니다.

하지만 과연 백트래킹을 돌려도 시간초과가 나지 않을까? 의문인 문제였습니다.

그래서 처음에선 2차원배열 백트래킹을 했는데 결과는....

시간초과가 났습니다.

 

그래서 예전 백트래킹 문제에서 백준에 치킨배달이라는 문제에서 필요한 인덱스를 

구조체배열을 사용해서 저장을 하고 그 인덱스만 이용하영 백트래킹을 하는 방식으로 

문제를 진행하였습니다.

 

그리고 이 문제에서 가장 중요한점은 한번만 결과값이 나오게 하라는것이였습니다.

본문에서는 두가지 방식으로 백트래킹 재귀 방식에서 한번만 나오게 하는법도 같이

소개하겠습니다.

 

스도쿠 소스코드를 보기전에 스도쿠란 무엇인가?

사이트에서도 잘 설정했지만 간단히 말하자면

 초록색 원이 칠해져있는 5를 넣는 위치에 가로 세로 방향으로 칠해진 노란색 길에 같은 수가 없어야하고

빨강 9칸의 네모칸에도 중복이 없이 1-9까지 숫자가 들어가야하는 규칙을 가지고 있습니다.

처음 가로 세로 방향을 확인하기위한 소스는

위의 그림과 같이 하면 되는데 

정사각형 9칸 네모를 확인을 처음에는 노가다로 했습니다.

그소스는 

if (y == 0) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 1) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 2) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)//3번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 3) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 4) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 5) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)//3번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 6) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 7) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 8) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)//3번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}

합쳐보았습니다.

 

    int cy = y / 3;
    int cx = x / 3;
    for (int i = cy * 3; i < (cy * 3) + 3; i++) {
        for (int j = cx *3; j < (cx * 3) + 3; j++) {
            if (Sudoku[i][j] == num) return false;
        }
    }

대신 배열 인덱스를 (0,0)~(8,8) 일때 가능한 소스입니다.

두개 소스를 잘 비교해서 보면 이해가 되실껍니다.

 

라스트. 전체소스를 보여드리겠습니다.

#include<stdio.h>
#include<stdlib.h>
using namespace std;
int Sudoku[9][9];
int N;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Sudo {
    int y, x;
};
Sudo board[81];
bool chk(int y, int x, int num) {
    //네방향 검사 
    for (int dir = 0; dir < 4; dir++) {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        while (0 <= ny && ny < 9 && 0 <= nx && nx < 9) {
            if (Sudoku[ny][nx] == num) return false;
            ny += dy[dir];
            nx += dx[dir];
        }
    }
    int cy = y / 3;
    int cx = x / 3;
    for (int i = cy * 3; i < (cy * 3) + 3; i++) {
        for (int j = cx *3; j < (cx * 3) + 3; j++) {
            if (Sudoku[i][j] == num) return false;
        }
    }
    return true;
}
void dfs(int idx) {
    if (idx == N) {
 
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    printf("%d ", Sudoku[i][j]);
                }
                printf("\n");
            }
            exit(0);
    }
        for (int num = 1; num <= 9; num++) {
            if (chk(board[idx].y, board[idx].x, num)) {
                Sudoku[board[idx].y][board[idx].x] = num;
                dfs(idx + 1);
                Sudoku[board[idx].y][board[idx].x] = 0;
            }
        }
}
 
int main(void)
{
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%d", &Sudoku[i][j]);
            if (Sudoku[i][j] == 0) {
                board[N].y = i;
                board[N].x = j;
                N++;
            }
        }
    }
    dfs(0);
    return 0;
}

의외로 간단한 소스같지만 좀 걸렸습니다.

여기서 마지막으로 한번만 출력을 하는게 포인트 인데 어떻게 했는지 알려드리자면 

헤더파일 #include<stdlib.h> 를 선언하고 exit(0)하게되면 되고, 헤더파일을 못쓰는데 그러면 방법이 없나?

하는분들도 계실수 있으므로 그렇다면 아래와 같이 쓰면됩니다.

 

flag 변수를 하나 선언하고 무조건 return 시키는 형식으로 해도 같은 결과가 나오니 참고해 주세요.

47분전이 exit(0);

32분전이 flag=1  return;

확실히 exit(0) 바로 끝내는것이 빠른걸 알수있습다. 물론 8ms 차이라 별차이가 없지만...

 

오늘도 긴글 읽어주시느라 고생하셨습니다. 감사합니다.