2580 번 문제 풀이

using Java 11

2580 문제 보기

import java.util.Scanner;

public class boj2580 {
	public static int[][] sudoku = new int[9][9];
	
	public static void main(String[]args) {
		// 입력
		Scanner in = new Scanner(System.in);
		for(int i = 0; i < 9; i++) {
			for (int j = 0; j < 9 ; j++) {
				sudoku[i][j] = in.nextInt();
			}
		}
		
		fillSudoku(0, 0);
	}
	public static boolean isPossible(int row, int col, int value) {
		//행 검사
		for(int i = 0; i < 9; i++) {
			if(sudoku[row][i] == value) {
				return false;
			}
		}
		//열 검사
		for(int i = 0; i < 9; i++) {
			if(sudoku[i][col] == value) {
				return false;
			}
		}
		//3x3 검사
		int rowSquare = (row/3) * 3;
		int colSquare = (col/3) * 3;
		
		for(int i = rowSquare; i < rowSquare + 3; i++) {
			for(int j = colSquare; j < colSquare + 3; j++) {
				if(sudoku[i][j] == value) {
					return false;
				}
			}
		}
		return true;
	}
	
	public static void fillSudoku(int row, int col) {
		if(row == 9) {
			for(int i = 0; i < 9; i++) {
				for (int j = 0; j < 9 ; j++) {
					System.out.print(sudoku[i][j]+" ");
				}
				System.out.println();
			}
			System.exit(0);
		}
		
		if(col == 9) {
			fillSudoku(row+1, 0);
			return;
		}
		
		if(sudoku[row][col] == 0) {
			for(int i = 1; i < 10; i++) {
				if(isPossible(row, col, i)) {
					sudoku[row][col] = i;
					fillSudoku(row, col+1);
				}
			}
			sudoku[row][col] = 0;
			return;
		}
		fillSudoku(row, col+1);
	}
} 

📍 isPossible 함수는 value 값이 그 자리에 위치 할 수 있나 확인하는 함수이다.
📍 재귀를 이용한 백트랙킹으로 해결 할 수 있었다.

✅ 틀린 이유
1. row == 9 인 경우 return; 해버리면 재귀를 깰 수가 없음
: return 하기 전에 출력하고 시스템 종료하는 쪽으로 방향을 바꿔서 해결했다.
2. 하나의 답을 타고 들어가다 '중간에 더 이상 채울 수 없는 경우' 고려하지 않음
: 이때 채우던 답을 다시 '0'으로 돌려두고 재귀를 깨고 나올 수 있도록 해야한다.
아래 코드를 추가하여 해결 했다.

sudoku[row][col] = 0;
return;

(참고: https://st-lab.tistory.com/119)