[Java] 백준 2239번 : 스도쿠

문제

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

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

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

입력

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

출력

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

제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++17: 180ms
  • Java 15: 528ms
  • PyPy3: 2064ms

예제 입력 1

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

예제 출력 1

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

 

소스코드

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 Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int [][]map;
	private static List<Point> list;
	
	static class Point {
		int r, c;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		bf=new BufferedReader(new InputStreamReader(System.in));
		map=new int[9][9];
		list=new ArrayList<>();
		
		for(int r=0;r<9;r++) {
			String s=bf.readLine();
			for(int c=0;c<9;c++) {
				map[r][c]=s.charAt(c)-'0';
				if(map[r][c]==0) list.add(new Point(r, c));	// 빈 칸을 list에 미리 저장해둠
			}
		}
		
		sudocu(0, map);
	}
	
	private static boolean sudocu(int count, int [][]map) {	// 중복 순열을 이용하여 가능한 값 탐색
		if(count==list.size()) {	// 빈 칸을 모두 채운 경우, 스도쿠를 출력하고 리턴
			for(int []r:map) {
				for(int c:r) System.out.print(c);
				System.out.println();
			}
			return true;
		}
		int [][]newMap=new int[9][9];
		copyMap(map, newMap);	// 탐색 과정에서 원래 map을 백업해주어 변경되지 않도록 함
		
		Point p=list.get(count);	// count번째 빈칸에 들어갈 값 탐색
		for(int i=1;i<=9;i++) {	// 1~9 중에서 가능한 숫자 찾기
			if(!check(p.r, p.c, i, newMap)) continue;	// i 못 들어감
			newMap[p.r][p.c]=i;	// 빈 칸에 들어갈 수 있는 값 대입
			if(sudocu(count+1, newMap)) return true;	// 다음 빈 칸에 들어갈 값 탐색(만약 빈 칸을 다 채운 경우 true를 리턴하며 재귀가 반복적으로 리턴되도록 함)
		}
		
		return false;
	}
	
	private static void copyMap(int [][]map, int [][]newMap) {
		for(int r=0;r<9;r++) newMap[r]=map[r].clone();
	}
	
	private static boolean check(int r, int c, int x, int [][]map) {	// 스도쿠 가로, 세로, 3x3을 확인하여 빈칸에 x가 들어갈 수 있는지 확인
		for(int i=0;i<9;i++) {
			if(map[r][i]==x) return false;	// 가로
			if(map[i][c]==x) return false;	// 세로
		}
		
		int startR=r-r%3;
		int startC=c-c%3;
		for(int R=startR;R<startR+3;R++) {	// 3x3
			for(int C=startC;C<startC+3;C++) {
				if(map[R][C]==x) return false;
			}
		}
		return true;
	}

}

1. 빈 칸을 list에 미리 저장해둡니다.

2. 중복 순열을 통해 빈 칸에 들어갈 수 있는 경우를 탐색합니다.

    2-1. 빈 칸에 들어갈 수 있는 경우를 확인하기 위해 가로, 세로, 3X3 영역을 확인합니다.

3. 빈 칸이 처음으로 모두 채워진 경우 리턴 및 출력해줍니다.