[백준] 2580. 스도쿠 (Java)

 

문제

2580번: 스도쿠

 

 

알고리즘

브루트포스, 백트래킹

 

 

풀이

빈 칸에 1부터 9까지 모든 수를 넣어보며 가능한 경우 다음 빈 칸으로 넘어가는 식으로

모든 빈 칸을 채웠을 때 결과를 출력한다.

 

1. 각 빈 칸의 좌표를 리스트에 저장한다.

2. 0번째 빈 칸부터 1~9까지 유효한 수를 찾는다.

3. 유효하다면 빈 칸을 그 수로 채우고, 다음 빈 칸으로 넘어간다.

4. 리스트의 마지막 빈 칸까지 채웠다면 결과를 출력한다.

---

유효성 확인

(y, x) 좌표에 num을 삽입할 수 있는지 확인한다.

 

각 빈 칸마다 유효성 검사를 하기 때문에 스도쿠판의 모든 가로, 세로, 정사각형을 확인할 필요없이

현재 채우려는 빈 칸의 가로, 세로, 정사각형만 확인하면 된다.

* 만약 모두 확인하면 시간초과가 발생한다.

 

1. 가로줄(board[y][i]) 에 삽입하려는 수가 이미 있다면 유효하지 않음

2. 세로줄(board[i][x]) 에 삽입하려는 수가 이미 있다면 유효하지 않음

3. 정사각형(board[y/3 * 3 + i/3][x/3 * 3 + i%3]) 에 삽입하려는 수가 이미 있다면 유효하지 않음

 

세 조건 모두 통과한다면 (y, x)에 num을 삽입해도 된다.

 

private static boolean check(int num, int y, int x) {
	int startY = y/3 * 3;
	int startX = x/3 * 3;
		
	for (int i = 0; i < 9; i++) {
		if (board[y][i] == num) return false;
		if (board[i][x] == num) return false;
		if (board[startY + i/3][startX + i%3] == num) return false;
	}
	return true;
}

 

 

 

코드

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

public class BOJ_2580 {

	static int[][] board;
	static List<Integer[]> blank;

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

		board = new int[9][9];
		blank = new ArrayList<>();

		for (int i = 0; i < 9; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 9; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				if (board[i][j] == 0)
					blank.add(new Integer[] { i, j });
			}
		}

		dfs(0);
	}

	static void dfs(int count) {
		if (count == blank.size()) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++)
					sb.append(board[i][j]).append(" ");
				sb.append("\n");
			}

			System.out.println(sb);
			System.exit(0);
		}

		for (int i = 1; i <= 9; i++) {
			Integer[] pos = blank.get(count);
			if (!check(i, pos[0], pos[1])) continue;

			board[pos[0]][pos[1]] = i;
			dfs(count + 1);
			board[pos[0]][pos[1]] = 0;
		}
	}

	private static boolean check(int num, int y, int x) {
		int startY = y/3 * 3;
		int startX = x/3 * 3;
		
		for (int i = 0; i < 9; i++) {
			if (board[y][i] == num) return false;
			if (board[i][x] == num) return false;
			if (board[startY + i/3][startX + i%3] == num) return false;
		}
		return true;
	}
}