문제 링크

성능 요약

메모리: 19840 KB, 시간: 352 ms

분류

백트래킹, 구현

제출 일자

2025년 1월 3일 22:08:35

문제 설명

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

풀이

느낀점

• 너무 실제 스도쿠처럼 풀어서 효율이 부족한 구현 방식이라고 생각했는데, 구현 알고리즘 문제가 맞았다..
• 비트마스킹을 생각보다 스스로 사용할 줄 알아서 놀랐다.
• 좀 더 깔끔한 코드가 있을 것 같다.

설계 : 10분

• 실제 스도쿠판, 복사본, 각 행의 숫자 사용현황(비트마스킹), 각 열의 숫자 사용현황(비트마스킹), 그리드 별 숫자 사용현황(비트마스킹), 성공 여부 등의 전역 변수를 두었다.
• 입력 중에 위 모든 변수를 초기화한다.
• 행 우선순회로 dfs를 돌며 작은 수부터 대입하고 다음 위치로 넘어가 모든 경우를 확인한다.
• 행, 열, 그리드 별 비트마스킹 현황을 업데이트하며 dfs를 재귀하기 때문에 이미 사용된 숫자에 대해 빠르게 제외하고 테스트할 수 있다.
• 행 인덱스가 9이상 넘어가면 완성된 스도쿠이므로 복사본의 상태를 실제 스도쿠판에 옮기고 성공 여부를 true로 수정해 dfs를 더이상 돌지 않도록 한다.

코드(Java)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 스도쿠_2239
 * Date: 2025.01.03
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int[][] sudoku;
	static int[][] test;
	static int[] row;
	static int[] col;
	static int[][] grid;
	static boolean complete;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		sudoku = new int[9][9];
		test = new int[9][9];
		grid = new int[3][3];
		row = new int[9];
		col = new int[9];

		for (int i = 0; i < 9; i++) {
			char[] input = br.readLine().toCharArray();
			for (int j = 0; j < 9; j++) {
				sudoku[i][j] = input[j] - '0';
				test[i][j] = sudoku[i][j];
				row[i] |= 1 << sudoku[i][j];
				col[j] |= 1 << sudoku[i][j];
				grid[i / 3][j / 3] |= 1<< sudoku[i][j];
			}
		}

		complete = false;
		dfs(0, 0);

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				sb.append(sudoku[i][j]);
			}
			sb.append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	private static void dfs(int r, int c) throws IOException {
		if (complete) return;
		if (r >= 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sudoku[i][j] = test[i][j];
				}
			}
			complete = true;
			return;
		}

		if (c >= 9) {
			dfs(r + 1, 0);
			return;
		}

		if (sudoku[r][c] != 0) {
			dfs(r, c + 1);
			return;
		}

		int visited = row[r] | col[c] | grid[r / 3][c / 3];
		int memoR = row[r];
		int memoC = col[c];
		int memoGrid = grid[r / 3][c / 3];
		for (int i = 1; i <= 9; i++) {
			if ((visited & 1 << i) != 0) continue;

			test[r][c] = i;
			row[r] |= 1 << i;
			col[c] |= 1 << i;
			grid[r / 3][c / 3] |= 1 << i;

			dfs(r, c + 1);

			row[r] = memoR;
			col[c] = memoC;
			grid[r / 3][c / 3] = memoGrid;
		}
	}
}