<Baekjoon> #2580 DFS_Sudoku c++
빈 칸을 채울 때 3x3 정사각형 내에서 숫자를 겹치지 않게 하는 부분과 시간 초과때문에 힘든 문제같다
vector<pair<int, int>>vp;
먼저 스도쿠 판에 숫자를 입력 받을 때 빈 공간 즉, 0으로 입력 받는 부분의 좌표를vp
에 저장하고 받을 때마다cnt++
를 해주어 전체 빈 공간의 좌표와 개수를 저장한다for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> board[i][j]; if (board[i][j] == 0) { vp.push_back(make_pair(i, j)); cnt++; } } }
void dfs (int idx)
idx
는 현재 몇 번 째 빈 공간의 좌표 쌍(vp[idx].first, vp[idx].second)
를 채우는 것인지 체크하기 위함으고dfs
함수의 종료 조건은idx==cnt
일 때 즉, 모든 빈 공간의 좌표를 채웠을 때이다if (idx == cnt) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) printf("%d ", board[i][j]); printf("\n"); } return; }
- 빈 공간에 숫자를 채워 넣기
빈 공간에는1~9
까지의 숫자가 들어갈 수 있으며 이 숫자가 들어갈 수 있는 숫자인지check
함수에서 유효성을 검사한 후 들어갈 수 있으면dfs(idx+1)
를 호출하여 다음 빈 공간에 대해1~9
까지 채워보며 유효성을 검사한다
만약1~9
까지 다 채웠는데 숫자를 채울 수 없으면 다시0
을 넣고 그 전의 빈칸부터 다시 채운다for (int i = 1; i <= N; i++) { board[vp[idx].first][vp[idx].second] = i; if (check(vp[idx])) dfs(idx + 1); if (found) return; } board[vp[idx].first][vp[idx].second] = 0;
3.
bool check(pair<int, int> p)
- 같은 행과 열에 지금 막 빈칸에 채워 넣은 숫자와 같은 숫자가 있는지 확인
for (int i = 0; i < N; i++) { if (board[p.first][i] == board[p.first][p.second] && i != p.second) return false; if (board[i][p.second] == board[p.first][p.second] && i != p.first) return false; }
- 3x3 정사각형 안에 지금 막 빈칸에 채워 넣은 숫자와 같은 숫자가 있는지 확인
int sq_y = p.first/3; int sq_x = p.second/3; //지금 좌표가 가로,세로로 몇 번 째 정사각형에 속하는지 알기 위해 //{0,1,2}= 0, {3,4,5}=1, {6,7,8}=2
for (int i = 3*sq_y; i <3*sq_y + 3; i++) { for (int j = 3*sq_x; j < 3*sq_x + 3; j++) { if (board[i][j] == board[p.first][p.second]) { if (i != p.first && j != p.second) return false; } } }
- 이 모든 조건에 걸리지 않으면
true
를return
전체 코드
#include <iostream> #include <vector> using namespace std; const int N = 9; int board[N][N]; int cnt = 0; bool found = false; vector<pair<int, int>>vp; bool check(pair<int, int> p) { int sq_y = p.first/3; int sq_x = p.second/3; for (int i = 0; i < N; i++) { if (board[p.first][i] == board[p.first][p.second] && i != p.second) return false; if (board[i][p.second] == board[p.first][p.second] && i != p.first) return false; } for (int i = 3*sq_y; i <3*sq_y + 3; i++) { for (int j = 3*sq_x; j < 3*sq_x + 3; j++) { if (board[i][j] == board[p.first][p.second]) { if (i != p.first && j != p.second) return false; } } } return true; } void dfs(int idx) { if (idx == cnt) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) printf("%d ", board[i][j]); printf("\n"); } return; } for (int i = 1; i <= N; i++) { board[vp[idx].first][vp[idx].second] = i; if (check(vp[idx])) dfs(idx + 1); if (found) return; } board[vp[idx].first][vp[idx].second] = 0; } int main() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> board[i][j]; if (board[i][j] == 0) { vp.push_back(make_pair(i, j)); cnt++; } } } dfs(0); return 0; }
Author And Source
이 문제에 관하여(<Baekjoon> #2580 DFS_Sudoku c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-2580-DFSSudoku-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)