백준 2239 - 스도쿠

Java

2239 번 - 스도쿠

문제

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

접근 방법

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[][] map;
	static boolean[][] row, col, box;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String str;
    	
    	map = new int[9][9];
    	row = new boolean[9][10];
    	col = new boolean[9][10];
    	box = new boolean[9][10];
    	
    	for(int i = 0; i < 9; i++) {
    		str = br.readLine();
    		for(int j = 0; j < 9; j++) {
    			map[i][j] = str.charAt(j) - '0';
    			if(map[i][j] != 0) {
    				row[i][map[i][j]] = true;
    				col[j][map[i][j]] = true;
    				box[findSquareIdx(i,j)][map[i][j]] = true;
    			}
    		}
    	}
    	DFS(0);
    	br.close();
	}
	
	static void DFS(int cnt) {
		if(cnt == 81) {
			for(int i = 0; i < 9; i++) {
	    		for(int j = 0; j < 9; j++) {
	    			System.out.print(map[i][j]);
	    		}
	    		System.out.println();
	    	}
			System.exit(0);
			return;
		}
		int y = cnt / 9;
		int x = cnt % 9;
		if(map[y][x] != 0) {
			DFS(cnt + 1);
		}
		else {
			for(int i = 1; i <= 9; i++) {
				if(!row[y][i] && !col[x][i] && !box[findSquareIdx(y,x)][i]) {
					map[y][x] = i;
					row[y][i] = true;
					col[x][i] = true;
					box[findSquareIdx(y,x)][i] = true;
					DFS(cnt + 1);
					map[y][x] = 0;
					row[y][i] = false;
					col[x][i] = false;
					box[findSquareIdx(y,x)][i] = false;
				}
			}
		}
	}
	
	static int findSquareIdx(int y, int x) {
		return (y / 3) * 3 + x / 3;
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점

없습니다.