[백준] 2580 스도쿠 - Backtracking / Java

• 문제 링크

2580번: 스도쿠

 

• 풀이 과정

입력받은 스도쿠 판의 값 중 비어있는 칸의 좌표를 제네릭이 Node 클래스인 List 객체 list 에 저장한다.

 

재귀 호출 함수 recur 에서 비어있는 좌표의 y, x 값을 list 에서 꺼내어

해당 값이 속한 가로, 세로축을 모두 탐색하고 3 * 3 정사각형을 탐색할 시작점의 좌표를 ny, nx 라 하였을 때

ny = y / 3 * 3, nx = x / 3 * 3 을 통하여 시작점을 구할 수 있다.

 

예시로 y, x 값이 2, 5 일 경우, int 형 정수 나눗셈에 의하여

(2 / 3) * 3 = 0 * 3 = 0, (5 / 3) * 3 = 1 * 3 = 3, 즉 탐색을 시작할 시작 좌표는 (0, 3) 이 된다.

 

이렇게 탐색을 끝낸 후 중복되는 값이 없다면 해당 값을 비어있는 좌표에 지정하고

다음 비어있는 좌표를 꺼내기 위해 idx + 1 을 매개변수로 전달하여 재귀 호출한다.

 

이때 해당 좌표에 지정한 값에 의하여 이와 교차되는 가로, 또는 세로의 값에

조건에 충족하는 값을 지정하지 못할 수 있으므로, 재귀 호출 후 map[y][x] = 0 으로 초기화한다.

 

idx == list.size() 일 시 비어있는 값을 모두 지정하였으므로 map 의 모든 요소를 정답으로써 출력하고,

flag 변수를 true 로 설정하여 다른 재귀 호출 함수를 종료시킨다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int[][] map = new int[9][9];
	static List<Node> list = new ArrayList<>();
	static boolean flag;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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());
				if (map[i][j] == 0)
					list.add(new Node(i, j));
			}
		}

		recur(0);
		
		bw.write(sb + "\n");
		bw.flush();
	}

	private static void recur(int idx) {
		if (idx == list.size()) {
			flag = true;
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) 
					sb.append(map[i][j] + " ");
				
				sb.append("\n");
			}
			
			return;
		}

		if (flag)
			return;

		int y = list.get(idx).y;
		int x = list.get(idx).x;

		for (int i = 1; i <= 9; i++) {
			if (check(y, x, i)) {
				map[y][x] = i;
				recur(idx + 1);
				map[y][x] = 0;
			}
		}
	}

	private static boolean check(int y, int x, int num) {
		for (int i = 0; i < 9; i++) {
			if (map[y][i] == num)
				return false;
			if (map[i][x] == num)
				return false;
		}

		int ny = y / 3 * 3;
		int nx = x / 3 * 3;

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

		return true;
	}

	private static class Node {
		int y, x;

		public Node(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

}