Link | 백준 2239번 문제 : 스도쿠
📌 About
이 문제는 백트래킹으로 풀 수 있는 문제이며 비트 연산을 통해 좀 더 빠른 연산이 가능하다.
우선 DFS 처럼 차례대로 빈 공간을 탐색하며 1부터 9까지 차례대로 삽입한다.
숫자를 삽입할 때마다 삽입 가능한 숫자인지 확인한다.
삽입이 불가능한 숫자이면 다음 숫자를 삽입한다
만약 모든 숫자를 삽입할 수 없다면 이전의 빈 공간으로 돌아가서 다음 숫자를 삽입한다.
만약 삽입 할 수 있는 숫자이면 다음 빈 공간으로 이동한다.
모든 공간이 삽입 가능한 숫자로 채워졌으면 모든 연산을 종료하고 현재 board를 출력한다.
📌 Solution
Step 0. Initialize
Field는 다음과 같이 선언한다.
private final List<Point> blanks = new ArrayList<>();
private final int[][] board = new int[9][9];
private final int[] rowNums = new int[9], colNums = new int[9];
private final int[][] blockNums = new int[3][3];| Variable | Content |
|---|---|
| blanks | 빈 공간의 좌표 정보를 저장한다. |
| board | 스도쿠 보드의 숫자 정보를 저장한다. |
| rowNums | 각 row의 어떤 숫자가 현재 적혀져 있는지 bit 값으로 저장한다. |
| colNums | 각 column의 어떤 숫자가 현재 적혀져 있는지 bit 값으로 저장한다. |
| blockNums | 각 block(3x3)의 어떤 숫자가 현재 적혀져 있는지 bit 값으로 저장한다. |
초기화는 다음과 같이 한다.
private void init() throws IOException {
for (int r = 0; r < 9; r++) {
int[] row = Arrays.stream(reader.readLine().split(""))
.mapToInt(Integer::parseInt).toArray();
for (int c = 0; c < 9; c++) {
if ((board[r][c] = row[c]) != 0) {
int visitBit = 1 << board[r][c] - 1;
rowNums[r] |= visitBit;
colNums[c] |= visitBit;
blockNums[r / 3][c / 3] |= visitBit;
} else blanks.add(new Point(r, c));
}
}
}읽은 값이 0이면 비어 있는 공간으로 blanks에 추가한다.
읽은 값이 0이 아니면 읽은 공가의 row, column, block에 bit 값을 업데이트 한다.
예를 들어 읽은 값이 3이면 1 << 3 - 1 shift 연산을 한다.
그러면 bit 값은 100이 된다.
여기서 각 row, column, block에 |= bit 연산을 하면 된다.
Step 1. 탐색
비어 있는 공간을 재귀적으로 탐색한다.
만약 탐색할 공간이 더 없으면 스도쿠가 완성된 것이므로 종료한다.
비어 있는 공간은 1부터 차례대로 삽입한다.
만약 가능한 탐색이면 다음 빈 공간을 탐색한다.
불가능한 탐색이면 다음 숫자를 삽입하고 다시 검증한다.
만약 1 ~ 9 모두 삽입할 수 없으면 이전 빈 공간으로 돌아가서 다음 숫자를 탐색한다.
private boolean search(int index) {
if (index == blanks.size()) return true;
int row = blanks.get(index).x, col = blanks.get(index).y;
int visit = rowNums[row] | colNums[col] | blockNums[row / 3][col / 3];
for (int num = 1; num <= 9; num++) {
int bit = 1 << (num - 1);
if ((visit & bit) != 0) continue;
board[row][col] = num;
rowNums[row] |= bit;
colNums[col] |= bit;
blockNums[row / 3][col / 3] |= bit;
if (search(index + 1)) return true;
board[row][col] = 0;
rowNums[row] &= ~bit;
colNums[col] &= ~bit;
blockNums[row / 3][col / 3] &= ~bit;
}
return false;
}백트래킹 방식임을 주의해야 한다.
숫자를 삽입하면 bit 연산을 통해 row, column, block을 업데이트 한다.
이후의 연산으로 불가능한 삽입임을 알게되면 현재 row, column, block을 업데이트 한다.
&= ~bit 연산은 해당 비트의 값을 0으로 업데이트하는 연산이다.
만약 XXX1XXX 이라는 비트열이 있을 때 &= ~(1000(비트)) 연산을 하면 XXX0XXX이 된다.
📌 Code
private final List<Point> blanks = new ArrayList<>();
private final int[][] board = new int[9][9];
private final int[] rowNums = new int[9], colNums = new int[9];
private final int[][] blockNums = new int[3][3];
public void solve() throws IOException {
init();
search(0);
result.append(
Arrays.stream(board).map(row ->
Arrays.stream(row)
.mapToObj(String::valueOf)
.collect(Collectors.joining()) + "\n"
).collect(Collectors.joining())
);
}
private void init() throws IOException {
for (int r = 0; r < 9; r++) {
int[] row = Arrays.stream(reader.readLine().split(""))
.mapToInt(Integer::parseInt).toArray();
for (int c = 0; c < 9; c++) {
if ((board[r][c] = row[c]) != 0) {
int visitBit = 1 << board[r][c] - 1;
rowNums[r] |= visitBit;
colNums[c] |= visitBit;
blockNums[r / 3][c / 3] |= visitBit;
} else blanks.add(new Point(r, c));
}
}
}
private boolean search(int index) {
if (index == blanks.size()) return true;
int row = blanks.get(index).x, col = blanks.get(index).y;
int visit = rowNums[row] | colNums[col] | blockNums[row / 3][col / 3];
for (int num = 1; num <= 9; num++) {
int bit = 1 << (num - 1);
if ((visit & bit) != 0) continue;
board[row][col] = num;
rowNums[row] |= bit;
colNums[col] |= bit;
blockNums[row / 3][col / 3] |= bit;
if (search(index + 1)) return true;
board[row][col] = 0;
rowNums[row] &= ~bit;
colNums[col] &= ~bit;
blockNums[row / 3][col / 3] &= ~bit;
}
return false;
}