https://www.acmicpc.net/problem/2580
풀이
처음에는 2차원 배열과 이중 for문을 통해 배열을 탐색해서 arr[i][j] == 0이면 1~9까지의 숫자를 넣고 check한 다음, 통과하면 재귀함수sudoku(i,j+1)를 호출해서 계속 탐색해서 마지막까지 오면 배열을 출력하도록 했다.
하지만 재귀함수를 호출하여 이중 for문을 쓰면 원하는 위치에서 탐색을 시작해도 배열의 탐색이 이루어지지 않는다. 매개변수 없이 재귀함수(sudoku())를 정해도 이전 재귀함수로 돌아가는 시점(return)도 정하기 매우 어렵다.
그래서 0인 위치를 ArrayList에 넣고, 그 위치에 1~9까지의 숫자를 넣고 check한 다음, 통과하면 재귀함수 sudoku(idx + 1)을 호출한다. 여기서 idx는 ArrayList의 인덱스다.
코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int[][] arr = new int[9][9];
static ArrayList<int[]> points;
static public boolean check(int row, int col) {
int n = arr[row][col];
arr[row][col] = -1; //체크할 때 현재 위치는 제외하기 위해 -1로 값을 변경한다
//같은 열이나 같은 행에서 같은 숫자가 있는지 체크
for (int idx = 0; idx < 9; idx++) {
if (arr[row][idx] == n || arr[idx][col] == n) {
return false;
}
}
//3x3 정사각형 안에 같은 숫자가 있는지 체크
int tmpRow = (row / 3) * 3;
int tmpCol = (col / 3) * 3;
for (int i = tmpRow; i < tmpRow+3; i++) {
for (int j = tmpCol; j < tmpCol+3; j++) {
if (arr[i][j] == n) {
return false;
}
}
}
arr[row][col] = n;
return true;
}
static public void sudoku(int idx) {
if (idx == points.size()) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
sb.append(arr[i][j] + " ");
sb.append("\n");
}
System.out.println(sb);
System.exit(0);
}
int[] tmp = points.get(idx);
for (int k = 1; k <= 9; k++) {
arr[tmp[0]][tmp[1]] = k;
if (check(tmp[0], tmp[1])) {
sudoku(idx + 1);
}
arr[tmp[0]][tmp[1]] = 0;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
points = new ArrayList<>();
for (int i = 0; i < 9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++) {
int n = Integer.parseInt(st.nextToken());
arr[i][j] = n;
if (n == 0)
points.add(new int[]{i, j});
}
}
sudoku(0);
}
}System.exit(0): 프로그램을 바로 종료한다.arr[tmp[0]][tmp[1]] = k;: for문 안에서 1~9까지 숫자를 집어넣는다.- 중요:
arr[tmp[0]][tmp[1]] = 0;: 다시 0을 집어넣어야 한다. 그렇지 않으면, 이전 함수로 돌아갈 때 9가 남겨져 있는 채로 return 될 수 있다.
수정한 버전
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int[][] arr = new int[9][9];
static ArrayList<int[]> points;
static public boolean check(int row, int col, int value) {
//같은 열이나 같은 행에서 같은 숫자가 있는지 체크
for (int idx = 0; idx < 9; idx++) {
if (arr[row][idx] == value || arr[idx][col] == value) {
return false;
}
}
//3x3 정사각형 안에 같은 숫자가 있는지 체크
int tmpRow = (row / 3) * 3;
int tmpCol = (col / 3) * 3;
for (int i = tmpRow; i < tmpRow+3; i++) {
for (int j = tmpCol; j < tmpCol+3; j++) {
if (arr[i][j] == value) {
return false;
}
}
}
return true;
}
static public void sudoku(int idx) {
if (idx == points.size()) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
sb.append(arr[i][j] + " ");
sb.append("\n");
}
System.out.println(sb);
System.exit(0);
}
int[] tmp = points.get(idx);
for (int k = 1; k <= 9; k++) {
if (check(tmp[0], tmp[1], k)) {
arr[tmp[0]][tmp[1]] = k;
sudoku(idx + 1);
}
arr[tmp[0]][tmp[1]] = 0;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
points = new ArrayList<>();
for (int i = 0; i < 9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++) {
int n = Integer.parseInt(st.nextToken());
arr[i][j] = n;
if (n == 0)
points.add(new int[]{i, j});
}
}
sudoku(0);
}
}check(row, col, value)- check 메서드를 통과한 후,
arr[tmp[0]][tmp[1]] = k; - 이렇게 하면 check 메서드에서
arr[row][col] = -1;을 하지 않아도 된다.
다른 풀이
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int[][] arr = new int[9][9];
static public boolean check(int row, int col, int value) {
//같은 열이나 같은 행에서 같은 숫자가 있는지 체크
for (int idx = 0; idx < 9; idx++) {
if (arr[row][idx] == value || arr[idx][col] == value) {
return false;
}
}
//3x3 정사각형 안에 같은 숫자가 있는지 체크
int tmpRow = (row / 3) * 3;
int tmpCol = (col / 3) * 3;
for (int i = tmpRow; i < tmpRow+3; i++) {
for (int j = tmpCol; j < tmpCol+3; j++) {
if (arr[i][j] == value) {
return false;
}
}
}
return true;
}
static public void sudoku(int row, int col) {
if (col == 9) {
sudoku(row + 1, 0);
return;
}
if (row == 9) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
sb.append(arr[i][j] + " ");
sb.append("\n");
}
System.out.println(sb);
System.exit(0);
}
if (arr[row][col] == 0) {
for (int k = 1; k <= 9; k++) {
if (check(row, col, k)) {
arr[row][col] = k;
sudoku(row, col + 1);
}
}
arr[row][col] = 0;
return;
}
sudoku(row, col+1);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < 9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
sudoku(0, 0);
}
}- 재귀함수:
sudoku(row, col)위치를 매개변수로 전달 sudoku(0, 0)부터 시작해서sudoku(row, col+1)을 재귀호출한다.col == 9이면sudoku(row+1, 0)return을 꼭 해야 한다. 아니면 런타임 에러(ArrayIndexOutOfBounds)가 난다.
