백준 - 2239번(스도쿠)
문제 출처: https://www.acmicpc.net/problem/2239
문제
- 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.
-
위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.
-
하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static List<int[]> target;
private static StringBuilder sb;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int[][] sudoku = new int[9][9];
target = new ArrayList<>();
for (int i = 0; i < 9; i++) {
char[] temp = reader.readLine().toCharArray();
for (int j = 0; j < 9; j++) {
sudoku[i][j] = temp[j] - '0';
if (sudoku[i][j] == 0) target.add(new int[] { i, j });
}
}
dfs(sudoku, 0);
System.out.println(sb);
}
private static void dfs(int[][] sudoku, int idx) {
if (sb != null) return;
if (idx == target.size()) {
sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(sudoku[i][j]);
}
sb.append("\n");
}
return;
}
int y = target.get(idx)[0];
int x = target.get(idx)[1];
boolean[] temp = new boolean[10];
checkCross(sudoku, temp, y, x);
checkInner(sudoku, temp, y / 3 * 3, x / 3 * 3);
for (int k = 1; k < 10; k++) {
if (!temp[k]) {
sudoku[y][x] = k;
dfs(sudoku, idx + 1);
sudoku[y][x] = 0;
}
}
}
// 가로, 세로 체크
private static void checkCross(int[][] sudoku, boolean[] temp, int r, int c) {
for (int i = 0; i < 9; i++) {
if (sudoku[r][i] != 0) temp[sudoku[r][i]] = true;
if (sudoku[i][c] != 0) temp[sudoku[i][c]] = true;
}
}
// 내부 3x3 사각형 체크
private static void checkInner(int[][] sudoku, boolean[] temp, int r, int c) {
for (int i = r; i < r + 3; i++) {
for (int j = c; j < c + 3; j++) {
if (sudoku[i][j] != 0) temp[sudoku[i][j]] = true;
}
}
}
}
- 상당히 오랜 시간이 걸려 문제를 풀었다.
- 처음 해결한 방법은 메모리와 시간이 상상을 초월하는 수준이었다.
- 특별히 깨닫게 된 것은, dfs를 이때까지는 더이상 진행할 수 없으면 다른 곳으로 가는 용도로만 사용했었는데, 다시 그 자리를 다른 값으로 채우는 방식도 가능함을 알게 되었다.
- 여러가지 쓸데없는 규칙들을 고려하느라 시간이 많이 걸렸는데, 좀 더 로직을 체계적으로 세우는 연습이 필요한 것 같다.
Author And Source
이 문제에 관하여(백준 - 2239번(스도쿠)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ghc1124/백준-2239번스도쿠저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)