📌 문제

[2580] 스도쿠

스도쿠는 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 리턴 ➡️ 해당 값 가능!

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;
}

(험난한 여정이였다..)