백준 2580 스도쿠 java

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

2580번: 스도쿠

백트래킹에서 가장 기초가 되는 문제이다.

대부분의 설명은 주석으로 대체한다.

sdoku[x][y] = i;
backTracking(index + 1, count + 1);
sdoku[x][y] = 0;

위 부분이 백트래킹의 핵심 부분이다.

백준 2580번에 기재된 출력예시대로 입력을 받는다면,

sdoku[x][y] = 0; 부분을 제외해도 결과물은 예시와 같게 출력된다.

하지만 올바른 정답은 아니다.

 

예를 들어

첫번째 가로줄 (0행) 에 비어있는 열이 0행과 5열  즉 (0,0) , (0,5) 가 비어있고,

(0,0) 에는 2과 4가 들어갈 수 있으며,  (0,5)에는 3,4가 들어갈 수 있다고 가정해보자.

처음에 (0,0)에 자리에 2를 채우고나서 (0,5)에 3을 채웠는데 조건에 충족하지 않아서 4를 채우려고 했지만

이것 또한 조건에 충족하지 않게 된다면,  (0,0)에 자리에 2 대신에 4를 넣어야하는데,

sdoku[x][y] =0 을 제외하게 된다면  앞서 채워넣었던 (0,5) 자리에 4가 위치하고있기때문에

(0,0)에 4를 채울수 없게된다.

 

 

 

 

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

public class 스도쿠 {

	static int[][] sdoku = new int[9][9];
	static ArrayList<int[]> list = new ArrayList<>();
	static boolean check;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				sdoku[i][j] = sc.nextInt(); // 스도쿠 번호를 입력받는다.
				if (sdoku[i][j] == 0) { // 입력받은 번호가 0 즉, 비어있다면 list에 추가시킨다.
					list.add(new int[] { i, j });
				}
			}
		}

		backTracking(0, 0); // inddex와 count의 시작은 0,0 이다.
		// -> index : 비어있는 자리를 저장한 list를 하나씩 꺼낼때 사용한다.
		// -> count : list의 크기(size)만큼 count가 도달한다면, 비어있는 자리에 숫자를 모두 채웠다는 뜻이다.
	}

	public static void backTracking(int index, int count) {
		if (count == list.size()) {
			print();
			check = true;
			return;
		}
		if (check)
			return;
		if (index >= list.size())
			return;

		int x = list.get(index)[0]; // 비어있는 자리의 x좌표
		int y = list.get(index)[1]; // 비어있는 자리의 y좌표

		for (int i = 1; i <= 9; i++) {
			if (check(x, y, i)) {
				sdoku[x][y] = i;
				backTracking(index + 1, count + 1);
				sdoku[x][y] = 0;
			}

		}
	}

	public static boolean check(int x, int y, int n) {
		for (int i = 0; i < 9; i++) {
			if (sdoku[x][i] == n)
				return false;
			// 가로(행)은 그대로 두면서, 열을 이동시키며 이미 중복된 숫자(n) 이 있다면 false.

			if (sdoku[i][y] == n)
				return false;
			// 세로(열)은 그대로 두면서, 행을 이동시키며 이미 중복된 숫자(n)이 있다면 false.
		}

		int nx = x / 3 * 3;
		int ny = y / 3 * 3;
		// (x / 3 * 3) 과 (y / 3 * 3)을 구하게 되면 , 비어있는 칸의 시작점을 구할 수 있다.
		// 예를들어 비어있는 칸의 좌표가 (1,4) 라면, 이 좌표의 시작 좌표는 (0, 3) 이 된다.
		// 따라서 3x3 의 중복 여부는 nx와 ny를 시작점으로 +3씩 해주면 구할 수 있게 된다.

		for (int i = nx; i < nx + 3; i++) {
			for (int j = ny; j < ny + 3; j++) {
				if (sdoku[i][j] == n)
					return false;
			}
		}

		return true;
	}

	public static void print() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				sb.append(sdoku[i][j] + " ");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}

}