[BOJ/JAVA] 백준 2239 : 스도쿠 (자바)

문제 정보

  문제명   - 스도쿠
  난이도   - 골드 IV
문제 번호 - 2239번

---

문제 링크

BOJ_G5_2239_스도쿠

2239번: 스도쿠

---

문제

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

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

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

---

입력

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

---

출력

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

---

예제 입력/출력

예제 입력	예제 출력
103000509 002109400 000704000 300502006 060000050 700803004 000401000 009205800 804000107	103000509 002109400 000704000 300502006 060000050 700803004 000401000 009205800 804000107

---

알고리즘 분류

● 구현
● 백트래킹

---

소스코드

package Lv3_Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
 * @author HanHoon
 * @category 구현, 백트래킹
 * https://www.acmicpc.net/problem/2239
 */
public class BOJ_G5_2239_스도쿠 {
	static int N = 9;
	static int[][] sdocu;
	static boolean complete = false;
	char[][] result = new char[9][9];
	public static boolean checkNumber(int y, int x, int num) {
		// 가로 세로 확인
		for (int i = 0; i < N; i++)
			if(sdocu[y][i] == num || sdocu[i][x] == num)
				return false;
		// 해당 블럭 내 확인
		int startY = y/3*3;
		int startX = x/3*3;
		for (int i = startY; i < startY+3; i++)
			for (int j = startX; j < startX+3; j++)
				if(sdocu[i][j] == num)
					return false;
		return true;
	}
	public static void backtracking(int count) {
		if(count == N*N) {
			complete = true;
			return;
		}
		int y = count / 9;
		int x = count % 9;
		if(sdocu[y][x] != 0) {
			backtracking(count+1);
		}else {
			// 1~9의 숫자 확인
			for (int i = 1; i <= 9; i++) {
				if(!checkNumber(y, x, i)) continue;
				sdocu[y][x] = i;
				backtracking(count+1);
				if(complete) return;
				sdocu[y][x] = 0;
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder str = new StringBuilder();

		sdocu = new int[9][9];
		// 값 입력
		for (int i = 0; i < N; i++) {
			String tmp = br.readLine();
			for (int j = 0; j < N; j++)
				sdocu[i][j] = tmp.charAt(j) - '0';
		}
		backtracking(0);
		// 값 출력
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++)
				System.out.print(sdocu[i][j]);
			System.out.println();
		}
		System.out.println(str.toString());
		br.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---