[백준] 2239 스도쿠 / 자바(Java)

문제

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

2239번: 스도쿠

 

---

해설

스도쿠를 해본 분이라면 상상만 했던 스도쿠를 자동으로 푸는 코드를 짜는 문제입니다.

구현문제로 큰 어려움 없이 필요한 동작들을 순서대로 실행하면 가능합니다.

 

1. 빈칸들을 확인하기

2. 빈칸에 들어갈 수 있는 수를 하나씩 넣어보기

3. 다음 빈칸을 확인하기

4. 2와3을 반복하며 모든 빈칸에 옳은 값을 넣은 경우 반복종료

 

사람과는 달리 컴퓨터는 예측이 아닌 모든 수를 넣고 가능한 경우를 찾아봅니다.

재귀를 사용하되 빈칸에 들어갈 수가 틀린경우 이전값을 초기화하고 다시 진행하므로 백트래킹방식으르 사용합니다.

 

 

1. 빈칸들을 확인하기

 

매번 빈 곳을 탐색하지 않기 위해 빈 곳들을 ArrayList에 넣어주어 탐색하기 편하도록 합니다.

 

2. 빈칸에 들어갈 수 있는 수를 하나씩 넣어보기

 

dfs함수를 통해 첫 빈 곳부터 그곳에 들어갈 수 있는 수를 먼저 검색합니다.

checker[]는 0~9까지의 인덱스로 각 위치별로 숫자를 넣을 수 있는지 check함수를 통해 가져옵니다.

 

3. 다음 빈칸을 확인하기

 

checker[]에서 가능한 값들을 넣고 dfs를 통해 빈곳 array의 idx를 하나 늘려서 다음 칸을 확인 가능하도록 넘겨줍니다.

 

4. 2와3을 반복하며 모든 빈칸에 옳은 값을 넣은 경우 반복종료

 

넘겨준 값이 성공한 경우 바로 true를 return해 추가 연산이 실행되지 않도록 합니다.

실패한 경우라면 빈 칸을 다시 0으로 초기화한 후 checker[]의 다음 숫자로 넘어갑니다.

모든 숫자가 실패한다면 완성할 수 없는 스도쿠로 false로 return합니다.

 

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
//134832	456
public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		

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

		for(int i=0;i<9;i++) {
			String inputLine = br.readLine();
			for(int j=0;j<9;j++) {
				board[i][j]=inputLine.charAt(j)-'0';
				// 1. 비어있는 부분의 위치를 empty리스트에 저장
				if(board[i][j]==0) empty.add(new int[] {i,j});
			}
		}

		dfs(board, empty, 0);
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<9;i++) {
			for(int j=0;j<9;j++) {
				sb.append(board[i][j]);
			}
		sb.append("\n");
		}
		System.out.println(sb);
		
	}
	
	static boolean dfs(int board[][], List<int[]> empty, int idx) {
		//모두 채워진 상태라면
		if(idx==empty.size()) {
			return true;
		}
		
		// 2. 해당 idx의 빈 칸에 들어갈 수 있는 숫자들을 가져옴
		boolean[] checker=check(empty.get(idx), board);
		for(int i=1;i<checker.length;i++) {
			// 들어갈 수 있다면
			if(!checker[i]) {
				// 3. 해당 위치에 들어갈 수 있는 숫자를 입력
				board[empty.get(idx)[0] ][empty.get(idx)[1]] = i;
				// 채워진 상태를 발견했다면 board를 되돌리는 일 없이 계속 리턴함
				if(dfs(board, empty, idx+1)) return true;
				// 실패했다면 0으로 되돌림
				board[empty.get(idx)[0] ][empty.get(idx)[1]] = 0;
			}
		}
		// 모든 가능성이 실패한 경우
		return false;
	}
	
	static boolean[] check(int[] point, int[][] board) {
		boolean[] checker = new boolean [10];
		
		// row 확인
		for(int i=0;i<9;i++) {
			checker[ board [point[0]][i] ]=true;
		}
		// col 확인
		for(int i=0;i<9;i++) {
			checker[ board [i][point[1]] ]=true;
		}
		
		// box 확인
		// 해당 위치의 3*3박스의 좌상단 값 가져옴
		int rbound = (point[0]/3)*3;
		int cbound = (point[1]/3)*3;
		for(int i=rbound;i<rbound+3;i++) {
			for(int j=cbound;j<cbound+3;j++) {
				checker[board[i][j]]=true;
			}
		}

		return checker;
	}
}