📌 문제
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
⬇️ 입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 d이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
⬆️ 출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
✔️ 제한
- 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
- Java: 292ms
💡 코드
✅ 게임 시작 전 9x9 스도쿠 판에 적힌 값을 크기가 9x9인 2차원 배열
arr[][]에 저장하고, 메서드sudoku(행, 열)메서드를 호출하여arr[행][열] = 0이라면 알맞은 값을 넣어준다.
sudoku(행, 열)if(row == 9): 한 행의 마지막 열(인덱스)까지 값을 채웠다면 다음 행으로 이동하여 첫번째 열부터 값을 탐색(sudoku(col+1, row))하고 함수를 종료한다.
if(col == 9): 마지막 행까지 모두 값을 채웠다면arr[][]에 저장된 값들을 출력한다. 이 때, 경우의 수가 여러가지인 경우 한가지만 출력해야하므로 처음 값을 채웠을 때 값을 출력하고System.exit(0)을 통해 실행을 강제종료 시켜줘야 한다.
if(arr[col][row]) == 0: 해당 위치의 값이 0이 아닌 경우에는 바로sudoku(col, row+1)을 통해 다음 열의 값을 찾고, 해당 위치의 값이 0일때만 1부터 9까지 돌아가면서 알맞은 값을 찾는다. 메서드isPossibel(행, 열, 값)을 통해 해당 값이 가능하다고 판별되면sudoku(col, row+1)을 호출하여 다음 열의 값을 찾는다. 9까지 돌았는데도 알맞은 값이 없다면arr[col][row]의 값을 0으로 초기화시키고 이전 단계로 돌아간다.
static void sudoku(int col, int row) {
if(row == 9) {
sudoku(col+1, 0); return;
}
if(col == 9) { // 출력
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[col][row] == 0) {
for(int j=1;j<=9;j++) {
if(isPossi**텍스트**ble(col, row, j)) {
arr[col][row] = j;
sudoku(col, row+1);
}
}
arr[col][row] = 0;
return;
}
sudoku(col, row+1);
}isPossible(행, 열, 값)- 첫번째 for문 : 같은 행에 값이 존재하면
false리턴 - 두번째 for문 : 같은 열에 값이 존재하면
false리턴 - 세번째 for문 : 3x3 직사각형 범위 안에 값이 존재하면
false리턴 - 위 세가지 조건에 걸리지 않으면
true리턴 ➡️ 해당 값 가능!
- 첫번째 for문 : 같은 행에 값이 존재하면
static boolean isPossible(int col, int row, int num) {
for(int i=0;i<9;i++) {
if(arr[col][i] == num) return false; // 같은 행
}
for(int i=0;i<9;i++) {
if(arr[i][row] == num) return false; // 같은 열
}
int sc = (col / 3) * 3;
int sr = (row / 3) * 3;
for(int i=sc;i<sc+3;i++) {
for(int j=sr;j<sr+3;j++) {
if(arr[i][j] == num) return false; // 3 x 3
}
}
return true;
}- 전체 코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] arr;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
arr = new int[9][9];
StringTokenizer st;
for(int i=0;i<9;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<9;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
sudoku(0, 0);
br.close();
bw.close();
}
static boolean isPossible(int col, int row, int num) {
for(int i=0;i<9;i++) {
if(arr[col][i] == num) return false; // 같은 행
}
for(int i=0;i<9;i++) {
if(arr[i][row] == num) return false; // 같은 열
}
int sc = (col / 3) * 3;
int sr = (row / 3) * 3;
for(int i=sc;i<sc+3;i++) {
for(int j=sr;j<sr+3;j++) {
if(arr[i][j] == num) return false; // 3 x 3
}
}
return true;
}
static void sudoku(int col, int row) {
if(row == 9) {
sudoku(col+1, 0); return;
}
if(col == 9) { // 출력
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[col][row] == 0) {
for(int j=1;j<=9;j++) {
if(isPossible(col, row, j)) {
arr[col][row] = j;
sudoku(col, row+1);
}
}
arr[col][row] = 0;
return;
}
sudoku(col, row+1);
}
}⌛ 시간초과의 원인! 출력 후에 return으로 종료해버리면 이전 단계로 돌아가서 모든 경우의 수를 찾게 되는데, 이 문제의 경우에는 한 가지의 경우만 출력하면 되므로 이전 단계로 돌아갈 필요없이
System.exit(0)로 강제종료 시켜줘야 한다! 이 때 강제종료는 단순 메서드 종료가 아닌 실행을 종료시키므로 출력을 먼저 수행하고 종료시켜야 한다.
if(col == 9) { // 출력
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
sb.append(arr[i][j] + " ");
}
sb.append("\n");
}
return;
}
(험난한 여정이였다..)
