[백준 2580번] 스도쿠

문제 링크: 2580번 제목

https://www.acmicpc.net/problem/2580

 

1. 스도쿠 판을 입력받으면서 빈 칸을 별도의 목록 empty에 저장한다.
2. empty의 각 칸에 대해서
2-1. 가능한 숫자의 목록을 구한다.
2-2. 해당 숫자를 집어넣고, 그 다음 칸으로 넘어간다.
2-3-1. 마지막 칸이 아님에도 가능한 숫자가 없다면, 되돌아간다.
2-3-2. 마지막 칸이고 가능한 숫자가 있다면, 첫 숫자를 넣고 종료한다.

되돌아갈 때, 반드시 집어 넣을 숫자를 삭제하여, 즉 다시 0으로 만들어주어 되돌아간 빈 칸에서 '가능한 숫자'가 '불가능한 숫자'가 되지 않도록 주의한다.

 

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;

class Pos {
	int row;
	int col;
	
	Pos(int row, int col) {
		this.row = row; this.col = col;
	}
}

public class Main {
	static int[][] board; // 스도쿠 판
	static ArrayList<Pos> empty = new ArrayList<Pos>(); // 빈 칸의 좌표 리스트
	
    /* 스도쿠 판을 인쇄 */
	static void printBoard() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				sb.append(board[i][j]);
				sb.append(" ");
			}
			sb.append("\n");
		}
		System.out.print(sb);
	}
	
    /* 수직으로 중복되는 숫자 제거 */
	static void vcheck(Pos pos, boolean[] avail) {
		Boolean[] nums = new Boolean[10];
		Arrays.fill(nums, true);
		int curCol = pos.col;
		
		for (int r = 0; r < 9; r++) {
			int alreadyInput = board[r][curCol];
			nums[alreadyInput] = false;
		}
		
		for (int i = 1; i <= 9; i++)
			avail[i] = avail[i] && nums[i];
	}
	
    /* 수평으로 중복되는 숫자 제거 */
	static void hcheck(Pos pos, boolean[] avail) {
		Boolean[] nums = new Boolean[10];
		Arrays.fill(nums, true);
		int curRow = pos.row;
		
		for (int c = 0; c < 9; c++) {
			int alreadyInput = board[curRow][c];
			nums[alreadyInput] = false;
		}
		
		for (int i = 1; i <= 9; i++)
			avail[i] = avail[i] && nums[i];
	}
	
    /* 3X3 사각형 내에서 중복되는 숫자 제거 */
	static void scheck(Pos pos, boolean[] avail) {
		Boolean[] nums = new Boolean[10];
		Arrays.fill(nums, true);
		
		// 현재 pos가 속한 사각형의 첫 번째 원소의 행과 열
		int bsFirstRow = pos.row/3*3;
		int bsFirstCol = pos.col/3*3;
		
		for (int r = bsFirstRow; r < bsFirstRow+3; r++) {
			for (int c = bsFirstCol; c < bsFirstCol+3; c++) {
				int alreadyInput = board[r][c];
				nums[alreadyInput] = false;
			}
		}
		
		for (int i = 1; i <= 9; i++)
			avail[i] = avail[i] && nums[i];
	}
	
    /* 가능한 숫자가 있는지 확인 */
	static boolean availEmpty(boolean[] avail) {
		for (int i = 1; i <= 9; i++)
			if (avail[i]) return false;
		return true;
	}
	
    /* empty[emptyIdx]에 가능한 숫자 채우기 */
	static void solve(int emptyIdx) {
		/* 마지막 빈 칸도 통과했다면 */
        // 종료 조건 1 시작: 마지막에 도달
		int emptyNum = empty.size();
		if (emptyIdx == emptyNum) {
			printBoard();
			System.exit(0);
		};
		// 종료 조건 1 끝
		
        
        /* 마지막 빈 칸 이전이라면 */
		// 이번에 숫자를 넣을 빈 칸
		Pos pos = empty.get(emptyIdx);
		
		// i가 pos에 들어갈 수 있으면 avail[i]=true
		boolean[] avail = new boolean[10];
		Arrays.fill(avail, true);
		vcheck(pos, avail);
		hcheck(pos, avail);
		scheck(pos, avail);
		
		// 종료 조건 2 시작: 가능한 숫자가 없음
		if (availEmpty(avail)) return;
		// 종료 조건 2 끝
		
		// 숫자 넣어보고 다음 위치 호출
		for (int i = 1; i <= 9; i++) {
			if (avail[i]) { // i가 pos에 들어갈 수 있다면
				board[pos.row][pos.col] = i; // i를 집어넣고,
				solve(emptyIdx+1); // 다음 빈 칸에 대해서 solve() 호출
				board[pos.row][pos.col] = 0; // 빈 칸으로 돌려준다.
			}
		}
	}
	
	public static void main(String[] args) {
		board = new int[9][9];
		Scanner sc = new Scanner(System.in);
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				int cur = sc.nextInt();
				board[i][j] = cur;
				
				if (cur == 0) empty.add(new Pos(i, j));
				// 빈 칸의 좌표를 empty에 추가
			}
		}
		sc.close();
		
		solve(0);
		
	}
}