2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
[ 백준 2580 ] 스도쿠 (C++)
백준의 스도쿠(2580) 문제이다. ( 문제 바로가기 ) [ 문제풀이 ] 1) 이 문제는 스도쿠 게임의 빈칸에 알맞은 숫자를 채워넣어야 하는 문제이다. 스도쿠 게임은 총 9x9 판위에서 이루어지며, 가로 9
yabmoons.tistory.com
| 0 |
1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
코드
- Step1) ROW, COL 배열에 각각 True, False값을 넣어준다
- ROW[i][map[i][j]]=true
- 각 행에 사용한 숫자(=map[i][j]))를 체크해준다
- COL[j][map[i][j]]=true;
- 각 열에 사용한 숫자를 체크한다.
- Square[(i/3)*3 + (j/3)][map[i][j]] = true
- (i/3)*3 + (j/3)
- (i,j)가 상위 표에서 어느 위치에 있는지 알려줌
- ex) (4,2)
- (4/3) * 3+ 2/3 = 3 번째 위치
- ex) (7,7)
- (7/3)*3 + 7/3 = 8번째 위치
- ex) (4,2)
- (i,j)가 상위 표에서 어느 위치에 있는지 알려줌
- (i/3)*3 + (j/3)
- dfs에서의 cnt
- int x = cnt/9;
- cnt=0~8
- x=0
- y=0~9
- cnt= 9~17
- x=1
- y=0~9
- cnt=18~26
- x=2...
- y=0~9...
- cnt=0~8
- 따라서 cnt=81 이란 것은 (0,0)부터 (9,9)까지 다 돈 것이다.
- int x = cnt/9;
- ROW[i][map[i][j]]=true
- 중요한 검색 로직!!
if (map[x][y] == 0)
{
for (int i = 1; i <= 9; i++)
{
if (row[x][i] == false && col[y][i] == false && square[(x / 3) * 3 + (y / 3)][i] == false)
{- 재귀 로직
- 들어갈 수 있는 가장 작은 i 값을 넣고 다 뺀뒤에 다 그다음 값을 넣고 돌리고 하는 식..!
row[x][i] = true;
col[y][i] = true;
square[(x / 3) * 3 + (y / 3)][i] = true;
map[x][y] = i;
dfs(cnt + 1);
map[x][y] = 0;
row[x][i] = false;
col[y][i] = false;
square[(x / 3) * 3 + (y / 3)][i] = false;
- map[i][j] = 0 을 만났을 때
- 해당 가로줄 검사
- 해당 세로줄 검사
- 해당 블럭(9개중1개) 검사
- 가능한 숫자 입력
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 9
/*
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0
*/
using namespace std;
void solution()
{
}
int map[9][9];
bool row[9][9];
bool col[9][9];
bool square[9][9];
void Print()
{
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX; j++)
{
cout << map[i][j] << " ";
}
cout << endl;
}
}
void dfs(int cnt)
{//cnt :
int x = cnt / 9;//x좌표
int y = cnt % 9;//y좌표
if (cnt == 81)
{
Print();
exit(0);
}
if (map[x][y] == 0)
{
for (int i = 1; i <= 9; i++)
{
if (row[x][i] == false && col[y][i] == false && square[(x / 3) * 3 + (y / 3)][i] == false)
{
row[x][i] = true;
col[y][i] = true;
square[(x / 3) * 3 + (y / 3)][i] = true;
map[x][y] = i;
dfs(cnt + 1);
map[x][y] = 0;
row[x][i] = false;
col[y][i] = false;
square[(x / 3) * 3 + (y / 3)][i] = false;
}
}
}
else dfs(cnt + 1);
}
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)
{
row[i][map[i][j]] = true; //i번째 가로줄에 n라는 숫자가 이미 존재합니다.
col[j][map[i][j]] = true; //j번째 세로줄에 n라는 숫자가 이미 존재합니다.
square[(i / 3) * 3 + (j / 3)][map[i][j]] = true; //a번째 사각형에 b라라는 숫자가 이미존재합니다.
}
}
}
dfs(0);
return 0;
}
'Algorithm' 카테고리의 다른 글
| [프로그래머스] 1차 캐시 c++ (0) | 2021.12.22 |
|---|---|
| [프로그래머스] 영어 끝말잇기 c++ (0) | 2021.12.22 |
| [백준] 2110 공유기 설치 (이분탐색) C++ (0) | 2020.10.06 |
| [백준 14888] 연산자 끼워넣기(C++, Java) (0) | 2020.09.09 |
| [백준 9536] 여우는 어떻게 울지? (Java) (0) | 2020.09.08 |