[백준] 자바 2239스도쿠

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

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

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

---

테스트 케이스

 

입력 1

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

출력 1

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

---

접근

처음 풀이

0인 곳을 모두 q에 넣어주고 넣을 수 있는 값만(가로, 세로, 3*3 종합하여 한자리만 비는 곳) 차례로 업데이트하면서 맵을 다돌면 맵을 업데이트하고 반복 => 시간초과

 

두번째 풀이

맵한번을 돌때 모든것을 해결하게끔 하니 시간초과 해결 0인점을 만났을때 가로,세로,대각선중 가능한 값을 넣아야함.

가능한 값을 넣을 수 없을경우 리턴하고 다른 경우를 탐색 =>해결

 

---

코드

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

public class Main {
	static int map[][];
	static StringBuilder sb = new StringBuilder();
	public static void fillSudoku(int row, int col) {
		if(col == 9) {
			fillSudoku(row+1,0);
			return;
		}
		else if(row == 9) {
			for(int i=0; i<9; i++) {
				for(int j=0; j<9; j++) {
					sb.append(map[i][j]);
				}
				sb.append("\n");
			}
			System.out.println(sb);
			System.exit(0);
		}
		if(map[row][col] == 0) {
			for(int i=1; i<=9; i++) {
				if(zeroCheck(row,col,i)) {
					map[row][col] = i;
					fillSudoku(row,col+1);
				}
			}
			//0에 들어갈값 못찾았음
			map[row][col] = 0;
			return;
		}
		fillSudoku(row,col+1);
	}
	public static boolean zeroCheck(int row, int col, int val) {
		//가로
		for(int i=0; i<9; i++) {
			if(map[row][i] == val) return false;
		}
		
		//세로
		for(int i=0; i<9; i++) {
			if(map[i][col] == val) return false;
		}
		
		//3*3
		int setRow = row/3*3;
		int setCol = col/3*3;
		for(int i=setRow; i<setRow+3; i++) {
			for(int j=setCol; j<setCol+3; j++) {
				if(map[i][j] == val) return false;
			}
		}
		return true;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		map = new int[9][9];
		for(int i=0; i<9; i++) {
			String temp = br.readLine();
			for(int j=0; j<9; j++) {
				map[i][j] = temp.charAt(j) -'0';
			}
		}
		fillSudoku(0,0);

		bw.flush();
		bw.close();
		br.close();
	}
}

---

주의

X