📍 문제 설명
💡 접근
0,0에서부터 모든 열을 확인후 모든 행을 탐색하는 방식으로 풀면 됐다.
근데 해당 지점에 잘못된 숫자가 들어갔을 때의 처리가 문제였다.
문제에서 제일 중요한 부분이 3군데 있었다.
1.이전 row가 잘못 채워졌을 경우에 되돌아가기 위한 return;
2.스도쿠가 채워졌을 경우 바로 출력시키고 종료하는 System.exit(0);
return;을 사용하면 안되는 이유는 마지막 탐색을 한다고 가정했을 때 스도쿠가 채워진다는 보장이 없기 때문임
3.들어갈 순 있지만 올바른 숫자가 아닐 때 다시 빈칸으로 만들고 + 되돌아가기 위한 return;
return이 없다면, 해당 자리를 채웠는데 실패한 경우 다시 돌아오고나서 또 다시 다음 열을 탐색하게됨
위 사진의 스도쿠를 본다면 0,0 올바른 값은 5이지만 맨 처음은 4가 들어간다.
483 219 675
25
(1,2)에 들어갈 수 있는 값이 존재하지 않으므로 재귀호출 되는 부분이 없다.
board[1][2] = 0으로 만들고 (1,1)로 다시 돌아가서 다른 값을 넣어서 호출해줘야한다.
x = 1, y = 1인 상태이고 i = 6인 상태에서 다른 값 넣어보기 / board[1][7] = 7이 들어간다.
483 219 675
275 346 981
196 78
(2,5)에 들어갈 수 있는 값이 존재하지 않으므로 재귀호출 되는 부분이 없다.
board[2][5] = 0으로 만들고 (2,3)로 다시 돌아가서 다른 값을 넣어서 호출해줘야한다.
(2,5)를 호출한 부분은 (2,4)이지만 값이 없을 때는 해당 지점의 값을 바꾸지 않고 바로 메서드 종료
x = 2, y = 3인 상태이고 i = 8인 상태에서는 이 지점에서도 들어갈 수 있는 값이 없다.
board[2][3] = 0으로 만들고 (1,9)로 다시 돌아가서 다른 값을 넣어서 호출해줘야한다.
(2,3)을 호출한 부분은 (2,2) (2,1) (2,0) 이지만 값이 없을 때는 바로 메서드 종료
여기서는 (2,0)에서 리턴이 되버리므로 (1,9)로 다시 돌아간다.
x = 1, y = 9인 상태이고 (1,9)를 호출한 부분은 (1,7)
x = 1, y = 7인 상태이고 i = 9인 상태에서는 들어갈 수 있는 값이 없다.
x = 1, y = 5인 상태이고 i = 6부터 확인해보면 6이 들어갈 수 있다.
483 219 675
275 36
여기까지가 1,3번 처리를 해준 것
2번에서 아무 처리를 안해준다면 일단 board[9][9] 를 탐색하므로 ArrayOutof~ 에러가 난다.
2번에서 Sytem.exit(0); 처리를 안해주고 return; 처리를 해준다면 계속 해서 스도쿠의 값들을 찾는데
마지막 값들의 탐색이니 처음에 높은 값들이 들어가 있을 거고 해당 스도쿠가 완성된 스도쿠라는 보장이 없다.
👩💻 코드
import java.util.*;
public class Main {
static int n, m, k;
static int[][] board,dis;
static int[] ch,compi,pm;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
//n = kb.nextInt();
//m = kb.nextInt();
board = new int[9][9];
for(int i = 0; i < 9; i++) {
for(int j = 0 ; j < 9; j++) {
board[i][j] = kb.nextInt();
}
}
//0,0인 지점 가로 줄 전부, 세로 줄 전부, 3x3칸에는 1~9만 있어야한다.
T.solution(0, 0);
}
private void solution(int x, int y) {
//열이 다 채워졌을 경우 다음 행을 확인
if(y == 9) {
solution(x + 1, 0);
return;
}
//행과 열이 다 채워졌을 경우 출력 후 바로 끝내버리기
if(x == 9) {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
System.exit(0);
}
//0일 때 1~9중 넣을 수 있는 수 탐색
if(board[x][y] == 0) {
for(int i = 1; i <= 9; i++) {
//행,열 3x3 중복되지 않는 값찾기
if(uniqueNumber(x, y, i)) {
//해당 숫자를 넣고 다음열 확인
board[x][y] = i;
solution(x, y+1);
}
}
board[x][y] = 0;
return;
}
solution(x, y + 1);
}
private boolean uniqueNumber(int x, int y, int value) {
// 같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사
for (int i = 0; i < 9; i++) {
if (board[x][i] == value) {
return false;
}
}
// 같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
for (int i = 0; i < 9; i++) {
if (board[i][y] == value) {
return false;
}
}
// 3*3 칸에 중복되는 원소가 있는지 검사
int set_row = (x / 3) * 3; // value가 속한 3x3의 행의 첫 위치
int set_col = (y / 3) * 3; // value가 속한 3x3의 열의 첫 위치
for (int i = set_row; i < set_row + 3; i++) {
for (int j = set_col; j < set_col + 3; j++) {
if (board[i][j] == value) {
return false;
}
}
}
return true; // 중복되는 것이 없을 경우 true 반환
}
}