[백준/BOJ] 백준 4574번 : 스도미노쿠
2021. 3. 13. 16:51ㆍ알고리즘 문제풀이
4574번: 스도미노쿠
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가
www.acmicpc.net
int used_block[10][10]; //[i,j] 도미노가 쓰였는지 확인
int used_row[9][10]; // 어떤 행에 해당 숫자가 쓰였는지 체크
int used_col[9][10]; // 어떤 열에 해당 숫자가 쓰였는지 체크
int used_mini[9][10]; //3X3 작은 보드에 해당 숫자가 쓰였는지 체크
를 통해 상황을 체크해가며 도미노를 넣어 보는 방식으로 문제를 해결했다
for (int i = 1; i <= 9; i++)
for (int j = i + 1; j <= 9; j++)
를 통해 [i][j]도미노가 point위치에 들어갈 수 있는지 판단하였다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int n;
int board[9][9];
int used_block[10][10]; //[i,j] 도미노가 쓰였는지 확인
int used_row[9][10]; // 어떤 행에 해당 숫자가 쓰였는지 체크
int used_col[9][10]; // 어떤 열에 해당 숫자가 쓰였는지 체크
int used_mini[9][10]; //3X3 작은 보드에 해당 숫자가 쓰였는지 체크
bool finish;
void Pre()
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
board[i][j] = 0;
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
used_block[i][j] = 0;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 10; j++)
{
used_row[i][j] = 0;
used_col[i][j] = 0;
used_mini[i][j] = 0;
}
finish = false;
}
//속해있는 3X3 보드의 번호를 반환한다
int mini_number(int row, int col)
{
int ret;
if (row < 3)
{
if (col < 3)
ret = 0;
else if (col < 6)
ret = 1;
else if (col < 9)
ret = 2;
}
else if (row < 6)
{
if (col < 3)
ret = 3;
else if (col < 6)
ret = 4;
else if (col < 9)
ret = 5;
}
else if (row < 9)
{
if (col < 3)
ret = 6;
else if (col < 6)
ret = 7;
else if (col < 9)
ret = 8;
}
return ret;
}
void Solve(int point)
{
if (finish == true)
return;
if (point == 81)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << board[i][j];
}
cout << "\n";
}
finish = true;
return;
}
int row = point / 9;
int col = point % 9;
//숫자가 있을때
if (board[row][col] != 0)
Solve(point + 1);
else
{
for (int i = 1; i <= 9; i++)
for (int j = i + 1; j <= 9; j++)
{
//쓰인 도미노일때
if (used_block[i][j] == 1)
continue;
//가로 확인
if (col + 1 < 9 && board[row][col] == 0 && board[row][col + 1] == 0)
{
if (used_row[row][i] == 0 && used_col[col][i] == 0 && used_row[row][j] == 0 && used_col[col + 1][j] == 0 && used_mini[mini_number(row, col)][i] == 0 && used_mini[mini_number(row, col + 1)][j] == 0)
{
used_block[i][j] = 1;
used_row[row][i] = 1;
used_col[col][i] = 1;
used_mini[mini_number(row, col)][i] = 1;
used_row[row][j] = 1;
used_col[col + 1][j] = 1;
used_mini[mini_number(row, col + 1)][j] = 1;
board[row][col] = i;
board[row][col + 1] = j;
//다음으로 넘어감
Solve(point + 1);
//원상복구
used_block[i][j] = 0;
used_row[row][i] = 0;
used_col[col][i] = 0;
used_mini[mini_number(row, col)][i] = 0;
used_row[row][j] = 0;
used_col[col + 1][j] = 0;
used_mini[mini_number(row, col + 1)][j] = 0;
board[row][col] = 0;
board[row][col + 1] = 0;
}
//해당 도미노 뒤집어서 확인
if (used_row[row][j] == 0 && used_col[col][j] == 0 && used_row[row][i] == 0 && used_col[col + 1][i] == 0 && used_mini[mini_number(row, col)][j] == 0 && used_mini[mini_number(row, col + 1)][i] == 0)
{
used_block[i][j] = 1;
used_row[row][j] = 1;
used_col[col][j] = 1;
used_mini[mini_number(row, col)][j] = 1;
used_row[row][i] = 1;
used_col[col + 1][i] = 1;
used_mini[mini_number(row, col + 1)][i] = 1;
board[row][col] = j;
board[row][col + 1] = i;
Solve(point + 1);
used_block[i][j] = 0;
used_row[row][j] = 0;
used_col[col][j] = 0;
used_mini[mini_number(row, col)][j] = 0;
used_row[row][i] = 0;
used_col[col + 1][i] = 0;
used_mini[mini_number(row, col + 1)][i] = 0;
board[row][col] = 0;
board[row][col + 1] = 0;
}
}
//세로 확인
if (row + 1 < 9 && board[row][col] == 0 && board[row + 1][col] == 0)
{
if (used_row[row][i] == 0 && used_col[col][i] == 0 && used_row[row + 1][j] == 0 && used_col[col][j] == 0 && used_mini[mini_number(row, col)][i] == 0 && used_mini[mini_number(row + 1, col)][j] == 0)
{
used_block[i][j] = 1;
used_row[row][i] = 1;
used_col[col][i] = 1;
used_mini[mini_number(row, col)][i] = 1;
used_row[row + 1][j] = 1;
used_col[col][j] = 1;
used_mini[mini_number(row + 1, col)][j] = 1;
board[row][col] = i;
board[row + 1][col] = j;
Solve(point + 1);
used_block[i][j] = 0;
used_row[row][i] = 0;
used_col[col][i] = 0;
used_mini[mini_number(row, col)][i] = 0;
used_row[row + 1][j] = 0;
used_col[col][j] = 0;
used_mini[mini_number(row + 1, col)][j] = 0;
board[row][col] = 0;
board[row + 1][col] = 0;
}
if (used_row[row][j] == 0 && used_col[col][j] == 0 && used_row[row + 1][i] == 0 && used_col[col][i] == 0 && used_mini[mini_number(row, col)][j] == 0 && used_mini[mini_number(row + 1, col)][i] == 0)
{
used_block[i][j] = 1;
used_row[row][j] = 1;
used_col[col][j] = 1;
used_mini[mini_number(row, col)][j] = 1;
used_row[row + 1][i] = 1;
used_col[col][i] = 1;
used_mini[mini_number(row + 1, col)][i] = 1;
board[row][col] = j;
board[row + 1][col] = i;
Solve(point + 1);
used_block[i][j] = 0;
used_row[row][j] = 0;
used_col[col][j] = 0;
used_mini[mini_number(row, col)][j] = 0;
used_row[row + 1][i] = 0;
used_col[col][i] = 0;
used_mini[mini_number(row + 1, col)][i] = 0;
board[row][col] = 0;
board[row + 1][col] = 0;
}
}
}
}
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int cnt = 0;
while (1)
{
cin >> n;
if (n == 0)
break;
Pre();
cnt++;
for (int i = 0; i < n; i++)
{
int u;
string lu;
int v;
string lv;
cin >> u >> lu >> v >> lv;
int u_row = lu[0] - 'A';
string u_col_temp = "";
u_col_temp += lu[1];
int u_col = stoi(u_col_temp) - 1;
int v_row = lv[0] - 'A';
string v_col_temp = "";
v_col_temp += lv[1];
int v_col = stoi(v_col_temp) - 1;
board[u_row][u_col] = u;
board[v_row][v_col] = v;
used_row[u_row][u] = 1;
used_col[u_col][u] = 1;
used_mini[mini_number(u_row, u_col)][u] = 1;
used_row[v_row][v] = 1;
used_col[v_col][v] = 1;
used_mini[mini_number(v_row, v_col)][v] = 1;
used_block[min(u, v)][max(u, v)] = 1;
}
for (int i = 1; i <= 9; i++)
{
string point;
cin >> point;
int point_row = point[0] - 'A';
string point_col_temp = "";
point_col_temp += point[1];
int point_col = stoi(point_col_temp) - 1;
board[point_row][point_col] = i;
used_row[point_row][i] = 1;
used_col[point_col][i] = 1;
used_mini[mini_number(point_row, point_col)][i] = 1;
}
cout << "Puzzle " << cnt << "\n";
Solve(0);
}
return 0;
}
'알고리즘 문제풀이' 카테고리의 다른 글
| [백준/BOJ] 백준 2800번 : 괄호 제거 (0) | 2021.03.13 |
|---|---|
| [백준/BOJ] 백준 1194번 : 달이 차오른다, 가자. (0) | 2021.03.13 |
| [백준/BOJ] 백준 9202번 : Boggle (0) | 2021.03.13 |
| [백준/BOJ] 백준 1525번 : 퍼즐 (0) | 2021.03.13 |
| [백준/BOJ] 백준 9935번 : 문자열 폭발 (0) | 2021.03.13 |