[Gold IV] 스도쿠 - 2580
성능 요약
메모리: 234072 KB, 시간: 716 ms
분류
백트래킹(backtracking)
문제 설명
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
- 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
- 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
스도쿠를 채우는 문제인데, 1~9까지의 수를 찾은 후에 해당 답이 틀렸을 경우 백트래킹을 하는 과정을 짜는 게 어려웠다.
백트래킹에 대해 다 이해하지 못해서인지 좀 더 공부가 필요할 것 같다
알맞은 수를 찾는 find함수를 정의하고 수를 찾지 못했을 경우 이전의 depth로 돌아가는 과정을 반복하도록 dfs를 짰다.
package Gold.g4;
import java.util.Scanner;
public class BOJ_2580_스도쿠 {
static int[][] sudoku = new int[9][9];
static int N = 0;
static int[][] memo;
static int cnt = 0;
static boolean found = false;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
sudoku[i][j] = sc.nextInt();
if (sudoku[i][j] == 0) {
N++;
}
}
// 입력
memo = new int[N][2]; // i, j의 좌표 담기
dfs(0);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
sb.append(sudoku[i][j]).append(" ");
sb.append("\n");
}
System.out.print(sb.toString());
}
static boolean find(int i, int j, int start) {
int r3 = i / 3 * 3;
int c3 = j / 3 * 3;
label: for (int k = start; k <= 9; k++) {
// 가로
for (int c = 0; c < 9; c++) {
if (sudoku[i][c] == k) {
continue label;
}
// 세로
if (sudoku[c][j] == k) {
continue label;
}
}
for (int r = r3; r < r3 + 3; r++)
for (int c = c3; c < c3 + 3; c++)
if (sudoku[r][c] == k) {
continue label;
}
sudoku[i][j] = k;
return true;
}
return false;
}
static void dfs(int depth) {
if (depth == N) {
return;
}
int i = 0;
int j = 0;
out: for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
if (sudoku[i][j] == 0)
break out;
memo[depth] = new int[] { i, j };
boolean check = find(i, j, 0);
if (check) {
dfs(depth + 1);
} else {
while (!check) {
depth--;
int start = sudoku[memo[depth][0]][memo[depth][1]];
sudoku[memo[depth][0]][memo[depth][1]] = 0;
check = find(memo[depth][0], memo[depth][1], start + 1); // 다음거부터 다시 탐색하기...
}
dfs(depth + 1);
}
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 14888 - 연산자 끼워넣기 (자바/Java) (1) | 2022.09.05 |
---|---|
[백준] 4563 - 리벤지 오브 피타고라스 (자바/Java) (0) | 2022.08.31 |
[백준] 9663 - N-Queen (자바/Java) (0) | 2022.08.26 |
[백준] 1676 - 팩토리얼 0의 개수 (자바/Java) (0) | 2022.08.26 |
[백준] 9375 - 패션왕 신해빈 (자바/Java) (0) | 2022.08.26 |