BOJ 문제 링크 : https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
스도쿠는 아래와 같은 규칙으로 빈칸을 채워나가는 게임이다.
1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3*3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
입력될때 빈칸은 0으로 입력된다.
입력으로 스도쿠 문제가 주어졌을때 알맞게 빈칸을 채운 9*9 행렬을 출력하는 문제이다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<iostream> | |
| #include<vector> | |
| using namespace std; | |
| int map[9][9]; | |
| vector<pair<int, int>> emptyBlock; | |
| vector<int> check(int y, int x) { | |
| vector<int> v; | |
| // 숫자들을 하나씩 대조해본다. | |
| for (int i = 1; i < 10; i++) { | |
| bool flag = false; | |
| for (int j = 0; j < 9; j++) { | |
| // 같은 행에 숫자들을 검사 | |
| if (map[y][j] == i) { | |
| flag = true; | |
| break; | |
| } | |
| // 같은 열에 숫자들을 검사 | |
| if (map[j][x] == i) { | |
| flag = true; | |
| break; | |
| } | |
| } | |
| if (flag) | |
| continue; | |
| // 같은 블락에 있는 숫자들을 검사 | |
| int firstY = (y / 3) * 3; | |
| int firstX = (x / 3) * 3; | |
| for (int j = firstY; j < firstY + 3; j++) { | |
| for (int k = firstX; k < firstX + 3; k++) { | |
| if (map[j][k] == i) { | |
| flag = true; | |
| break; | |
| } | |
| } | |
| if (flag) | |
| break; | |
| } | |
| if (flag) | |
| continue; | |
| // 중복되는게 하나도 없으면 v에 삽입 | |
| v.push_back(i); | |
| } | |
| return v; | |
| } | |
| bool solve(int it) { | |
| // 스도쿠 문제를 해결했다면 return true; | |
| if (it == emptyBlock.size()) | |
| return true; | |
| // 다음 0인 칸을 찾는다. | |
| int y = emptyBlock[it].first; | |
| int x = emptyBlock[it].second; | |
| // 해당 칸에 들어갈 수 있는 숫자들을 찾는다. | |
| vector<int> valid = check(y, x); | |
| // 해당 칸에 들어갈 수 있는 수가 없다면 그 전 과정이 잘못됨 | |
| if (valid.empty()) | |
| return false; | |
| // 들어갈 수 있는 수들을 하나씩 대입 | |
| for (int k = 0; k < valid.size(); k++) { | |
| map[y][x] = valid[k]; | |
| if (solve(it + 1) == true) | |
| return true; | |
| map[y][x] = 0; | |
| } | |
| // 이전 단계의 숫자 선택이 잘못된 경우 | |
| return false; | |
| } | |
| int main() { | |
| for (int i = 0; i < 9; i++) { | |
| for (int j = 0; j < 9; j++) { | |
| cin >> map[i][j]; | |
| if (map[i][j] == 0) | |
| emptyBlock.push_back(make_pair(i, j)); | |
| } | |
| } | |
| solve(0); | |
| for (int i = 0; i < 9; i++) { | |
| for (int j = 0; j < 9; j++) | |
| cout << map[i][j] << ' '; | |
| cout << endl; | |
| } | |
| } |
코드 원본: https://github.com/sbl133/BOJ/blob/main/%232580.cpp
GitHub - sbl133/BOJ
Contribute to sbl133/BOJ development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
'Algorithm > BOJ' 카테고리의 다른 글
| [BOJ] 백준 1987번 알파벳 c++ (0) | 2022.04.19 |
|---|---|
| [BOJ] 백준 1011번 Fly me to the Alpha Centauri c++ (0) | 2022.04.17 |
| [BOJ] 백준 2206번 벽 부수고 이동하기 c++ (0) | 2022.04.16 |
| [BOJ] 백준 7576번 토마토 c++ (0) | 2022.04.09 |
| [BOJ] 백준 1759번 암호 만들기 c++ (0) | 2022.02.15 |
