https://www.acmicpc.net/problem/2580
빈 칸에 들어갈 숫자를 구하는 과정까지는 빠르게 구현했는데, 백트래킹 알고리즘 구현에서 빈 칸에 들어갈 숫자를 실시간으로 구해서 대입했어야 하는데 그 부분을 실수해서 디버깅에 한참을 소비하고 말았당
문제 해결 과정
착안
빈 칸으로 표시된 칸마다 재귀적으로 현재 칸에 넣을 수 있는 숫자를 넣고, 넣을 수 있는 숫자가 없는 경우에는 이전 단계로 돌아가 다른 숫자를 넣도록 하는 백트래킹 알고리즘을 통해 문제를 해결하고자 하였다.
구현
$i$행 $j$열의 빈 칸을 채울 때, $i$ 번째 행(가로줄)과 $j$ 번째 행(세로줄) 및 $i$행 $j$열을 포함하는 굵은 선으로 구분된 사각형 각각에 대해 1부터 9까지의 숫자가 중복되지 않고 하나씩 나타나야 하므로, 빈 칸에 넣을 수 있는 숫자를 찾는 함수를 아래와 같이 비트마스킹(bitmasking) 기법을 활용하여 구현해보았다.
가로줄, 세로줄, 3 $\times$ 3 크기의 사각형에 이미 포함된 숫자들을 비트 표현으로 저장할 int 형의 변수를 mask라고 하고, 숫자 $x \space (1 \le x \le 9)$를 $2^{x-1}$ 자리의 비트와 대응시킨다고 하면, 왼쪽 시프트 연산자(<<)와 비트 OR 연산자(|)를 활용해 아래와 같이 비트마스킹을 할 수 있다.
mask |= 1 << (x - 1); // x는 가로줄, 세로줄, 3 x 3 사각형에서
// 빈칸이 아닌 곳에 포함되어 있는 숫자
따라서 $i$행 $j$열의 빈 칸과 연관되는 가로줄, 세로줄, 굵은 선으로 구분된 사각형에 포함된 숫자들에 대해 다음과 같이 반복문을 구현하여 mask 변수에 포함 여부를 마스킹 한다.
- 가로줄, 세로줄 탐색: (가로줄) 행 번호를 $i$로 고정하고 열 번호 $k$에 대해 반복문 실행, (세로줄) 열 번호를 $j$로 고정하고 행 번호 $k$에 대해 반복문을 실행
- 굵은 선으로 구분된 사각형 탐색: int 형의 나눗셈 특성을 활용해 $i$ / 3 * 3 번째 행부터 $i$ / 3 * 3 + 2 번째 행까지, $j$ / 3 * 3 번째 열부터 $j$ / 3 * 3 + 2 번째 열까지 반복문을 실행
가로줄, 세로줄, 굵은 선으로 구분된 사각형 내의 숫자들에 대해 모두 마스킹이 완료되면 mask 변수에 저장된 비트를 반전시킨 다음, 숫자 $m$이 포함되어있는지의 여부를 아래와 같이 확인할 수 있다.
~mask >> (m - 1) & 1; // 해당 값이 1 (true)이면 숫자 m을 빈칸에 넣을 수 있다
// 해당 값이 0 (false)이면 숫자 m은
// 가로줄, 세로줄 또는 3 x 3 사각형 내에 이미 포함된 경우이다
위와 같이 함수를 구현해 활용하면 백트래킹(backtracking) 알고리즘에 기반해 모든 빈칸에 대해 순차적으로 숫자를 넣어본 다음, 넣을 수 있는 숫자가 없으면 이전 과정으로 되돌아가는 방법으로 문제를 해결할 수 있다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
#include <iostream>
#include <vector>
using namespace std;
struct Coord
{
int Row;
int Col;
};
int Sudoku[9][9];
vector<Coord> Blanks;
int Filled;
bool IsFillable(Coord coord, int n)
{
int row = coord.Row, col = coord.Col;
int mask = 0;
for (int i = 0; i < 9; i++)
{
if (Sudoku[row][i])
mask |= 1 << (Sudoku[row][i] - 1);
if (Sudoku[i][col])
mask |= 1 << (Sudoku[i][col] - 1);
}
int rStart = row / 3 * 3;
int cStart = col / 3 * 3;
for (int i = rStart; i < rStart + 3; i++)
for (int j = cStart; j < cStart + 3; j++)
if (Sudoku[i][j])
mask |= 1 << (Sudoku[i][j] - 1);
return ~mask >> (n - 1) & 1;
}
void FillBlanks()
{
Coord blank = Blanks[Filled];
for (int i = 1; i <= 9; i++)
{
// fill the blank if i is a fillable number
if (IsFillable(blank, i))
{
Sudoku[blank.Row][blank.Col] = i;
Filled++;
if (Filled < Blanks.size())
FillBlanks(); // recursion
}
}
// backtrack to blank
if (Filled != Blanks.size())
{
Sudoku[blank.Row][blank.Col] = 0;
Filled--;
}
}
int main()
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
{
cin >> Sudoku[i][j];
if (!Sudoku[i][j])
Blanks.push_back(Coord{ i, j });
}
if (!Blanks.empty())
FillBlanks();
// print
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
cout << Sudoku[i][j] << " ";
cout << "\n";
}
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 2629번: 양팔저울 (0) | 2023.12.15 |
---|---|
[Baekjoon] 11967번: 불켜기 (0) | 2023.12.14 |
[Baekjoon] 동전 뒤집기 (0) | 2023.12.09 |
[Baekjoon] 9084번: 동전 (1) | 2023.12.07 |
[Baekjoon] 1063번: 킹 (2) | 2023.12.05 |
댓글