BOJ_G4_2239

📁 [G4_2239] 스도쿠

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	static int[][] map;
	static ArrayList<int[]> list;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 판
		map = new int[9][9];

		list = new ArrayList<int[]>();

		for (int i = 0; i < 9; i++) {
			String str = br.readLine();
			String[] sstr = str.split("");
			for (int j = 0; j < 9; j++) {
				map[i][j] = Integer.parseInt(sstr[j]);

				if (map[i][j] == 0) {
					list.add(new int[] { i, j });
				}
			}
		}

		perm(0);

	}

	// 순열
	static void perm(int idx) {

		// 기저조건
		if (list.size() == idx) {
			output();
            // 즉 시 종 료 !!!
			System.exit(0);
		}

		// 좌표 기록
		int x = list.get(idx)[1];
		int y = list.get(idx)[0];

		// 1 ~ 9 까지 사용된 숫자 체크 true
		boolean[] v = new boolean[10];

		// 행확인
		check_row(x, y, v);
		// 열확인
		check_col(x, y, v);
		// 3*3 확인
		int startX = (x / 3) * 3;
		int startY = (y / 3) * 3;
		check(startX, startY, v);
		
		for(int i=1; i<10; i++) {
			// 아직 수를 넣지 않은 자리면
			if(!v[i]) {
				map[y][x] = i;
				perm(idx+1);
				// 백트래킹
				map[y][x] = 0;
			}
		}

	}

	// 3*3 배열 확인
	static void check(int x, int y, boolean[] v) {
		for (int i = y; i < y + 3; i++) {
			for (int j = x; j < x + 3; j++) {
				if (map[i][j] != 0) {
					v[map[i][j]] = true;
				}
			}
		}
	}

	// 행확인 -> 이미 본인 값이 있으면 false , 아니면 true
	static void check_row(int x, int y, boolean[] v) {
		for (int i = 0; i < 9; i++) {
			if (map[y][i] != 0)
				v[map[y][i]] = true;
		}
	}

	// 열확인 -> 이미 본인 값이 있으면 false , 아니면 true
	static void check_col(int x, int y, boolean[] v) {
		for (int i = 0; i < 9; i++) {
			if (map[i][x] != 0)
				v[map[i][x]] = true;
		}
	}

	// 스도쿠 출력하는 부분
	static void output() {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
}

🤔 나의 생각

이 문제는 스도쿠 문제이다. 사실 행, 열, 33 배열 일때 1~9가 맞아야된다 말고는 다른 쓸 만한 스도쿠 푸는 정보가 필요없다.
사실 스도쿠를 실제로 풀 때는 1~9 숫자가 가장 많이 분포해있는 정보부터 푸는 팁이 있는데 그 팁은 별로 쓸모 없는 것 같다.. ㅋㅋ
3가지 조건 ( 행, 열, 33 배열)을 성립하는지 확인하기 위해 메서드로 따로 빼놓았고,
좌표를 list에 저장해서 순열을 이용하였다.
순열이라고 생각한 이유는 간단하게 3가지 조건안에서 9중에 1가지 숫자를 선택해야한다고 생각했기 때문이다. 그리고 순서도 상관이 있고.
boolean 배열을 가지고 1~9 까지 아직 쓰이지 않은 수를 넣고 다시 빼고 백트래킹 하고를 반복해서 최적의 해를 구해주었다.
키포인트 !!
문제에서 가장 최소인 경우를 구하라고 되어있는데 이 부분은 처음 순열의 기저조건을 만나면 바로 출력해서 끝내도록 하여 해결하였다.
이 부분이 없으면 답이 안 나올것이다. 다 0 인경우 해가 계속해서 나온다… ㅎ