[2580번] 스도쿠 (백트래킹, 3*3나누기)

---

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

처음에 떠오른 방법은 열,행,대각선 각각 비교한 후
자리에 넣을 수 있는 숫자 후보들을 구한다.
그 후보들이 1개이면 그 자리를 먼저 채운다.
그리고 나머지 자리에 대해서 비교하면서 채운다.
보통 나는 스도쿠를 위와 같은 방식으로 푸는데 코드로 로직을 짤 때는 고려사항이 너무 많은 것 같아서 이 방법이 답은 아닌 것 같다.
어떻게 풀어야 하는걸까

각 자리에 1부터 9까지 모두 다 넣어보면서 탐색을 하다가 안되면 2로 넘어가는 식으로 풀면된다.
반복이 적어서 가능할듯.

아래와 같이 3*3구간 내에서 첫 시작 좌표로 돌아가게 하는 공식을 생각해내는 게 이 문제의 히든 포인트이지 않나 생각이 든다.

int nowRow = (row / 3) * 3;
int nowCol = (col / 3) * 3;

공식 잘 기억해두자.

그리고 백트래킹 사용한다. 이전 단계 즉 바로 위로 올라가는 것 기억하기!!

//탐색
if (map[x][y] == 0) {
		for (int k = 0; k < 9; k++) {
			if (isP(x, y, k)) { //행,열,대각선이 모두 만족할 경우
				map[x][y] = k; //자리를 값으로 채운다.
				getFinalNumber(x, y + 1);
			}
		}
        
		map[x][y] = 0; //백트래킹
		return;
}

그리고 두 코드는 같은 결과를 도출한다.

---

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

public class Main {
	//스도쿠

	static int[][] map = new int[9][9];

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

		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		getFinalNumber(0, 0);

	}

	static void getFinalNumber(int x, int y) { //탐색 시작

		//다음 행 실행
		if (y == 9) {
			getFinalNumber(x + 1, 0);
			return;
		}

		if (x == 9) { //모든 map이 다 채워졌을 경우 map 출력
			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);
		}

		//탐색
		if (map[x][y] == 0) {
			for (int k = 1; k <= 9; k++) { //K는 1-9까지로 설정!
				if (isP(x, y, k)) { //행,열,대각선이 모두 만족할 경우
					map[x][y] = k; //자리를 값으로 채운다.
					getFinalNumber(x, y + 1);
				}
			}
			map[x][y] = 0; //백트래킹
			//isP하다면 다음 열로 넘어가지만 isP하지 않다면 0으로 바꾸고 이전 단계로 돌아간다.
			return;
		}

		getFinalNumber(x, y + 1);

	}

	static boolean isP(int row, int col, int num) {

		for (int k = 0; k < 9; k++) {
			if (map[row][k] == num || map[k][col] == num) { //1. 행과 열 판단
				return false;
			}
		}

		//2. 대각선 판단
		// num이 포환됨 3*3의 첫 시작 좌표
		int nowRow = (row / 3) * 3;
		int nowCol = (col / 3) * 3;

		for (int i = nowRow; i < nowRow + 3; i++) {
			for (int j = nowCol; j < nowCol + 3; j++) {
				if (map[i][j] == num) {
					return false;
				}
			}
		}

		return true;
	}


}

---

---

코드가 이해는 되는데 혼자서 시간내에 풀 수 있냐? 는 아닌 것 같다.
이 유형은 문제 많이 풀어서 익숙해져야 할듯함