백준[2580] 스도쿠

백준 2580 스도쿠

Language

Java 사용

Input

9*9 스도쿠 상태를 입력받는다. 빈칸은 0으로 표기된다.

Output

우리 모두가 아는 스도쿠의 규칙을 따르며 스도쿠의 빈칸을 채워나간 후, 스도쿠 정답을 출력한다.

IDEA

1. 보드의 상태를 입력받고, 빈칸의 좌표는 ArrayList에 추가해준다.

2. 빈칸의 좌표를 하나씩 꺼내서 해당 좌표에 1~9를 차례대로 넣어본다.

3. 만약 넣은 숫자가 스도쿠의 규칙을 위반하지 않는다면 다음 빈칸 좌표를 넣는다.

4. 만약 넣은 숫자가 스도쿠의 규칙을 위반한다면 이전의 빈칸 좌표로 돌아가 다시 숫자를 넣어본다.

5. 모든 빈칸의 좌표를 채워서 스도쿠를 완성할 때 가지 2~4를 반복한다.

CODE

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

//좌표 정보를 담는 class Point
class Point{
	int x,y;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	
	public static int[][] board; // board 상태를 저장
	public static ArrayList<Point> zero; //빈칸 좌표를 담는 ArrayList
	static BufferedWriter bw; //출력을 위해 BufferedWriter 선언
	
	public static void main(String[] args) throws IOException {
		
		//INPUT
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String str;
		String[] str_split;
		zero = new ArrayList<>();
		
		board = new int[9][9];
		
		//board 상태 저장
		for(int i = 0; i<9;i++) {
			str = br.readLine();
			str_split = str.split(" ");
			for(int j = 0; j<9;j++) {
				board[i][j] = Integer.parseInt(str_split[j]);
				if(board[i][j] == 0) { //0이라면 해당 좌표를 zero 리스트에 추가한다.
					zero.add(new Point(i,j));
				}
			}	
		}
		
		//0의 위치 파악하고, 가로 세로, 정사각형 파악
		//0에 넣을 수 있는 숫자를 파악한 후 넣어보고 다음 0 탐색. 만약 빈칸에 1~9까지 모두 안들어가면
		//백트래킹을 하여서 이전 0에 다른 숫자 넣어볼 것.
		
		sudoku(0);
		
		br.close();
	}
	
	public static void sudoku(int idx) throws IOException{ //탐색할 x,y좌표의 index와 숫자를 집어넣은 개수를 입력받음
				
		//만약에 스도쿠 정답이 나온다면 해당 정답인 board를 모두 출력해주고
		//자바 강제 종료
		if(zero.size() == idx) {
			for(int i = 0; i<9;i++) {
				for(int j = 0; j<9;j++) {
					bw.write(board[i][j]+" ");
				}
				bw.write("\n");
			}
			bw.flush();
			System.exit(0);
		}
		
		int tmpX = zero.get(idx).x; // 빈칸의 x좌표
		int tmpY = zero.get(idx).y; // 빈칸의 y좌표
		
		for(int i = 1; i<=9;i++) {
			
			//안전하다면 (스도쿠의 규칙을 위배하지 않는다면)		
			if(is_ok(idx,i)) {
				board[tmpX][tmpY] = i; //board에 해당 숫자를 넣고
				sudoku(idx+1); //다음 zero 부분을 파악해준다.
				board[tmpX][tmpY] = 0; //backtrack한다. (다시 빈칸으로 초기화)
			}
		}
		
		
	}
	
	//유효성 검사 함수
	public static boolean is_ok(int idx,int num) {
		int tmpX = zero.get(idx).x;
		int tmpY = zero.get(idx).y;
		
		
		for(int i = 0;i<9;i++) {
			//같은 행에 같은 숫자가 존재하는지 검사
			if(board[tmpX][i] == num) return false;
			//같은 열에 같은 숫자가 존재하는지 검사
			if(board[i][tmpY] == num) return false;
		}

		
		//3*3 박스 안에 같은 숫자가 존재하는지 검사
		int row = (tmpX/3)*3;
		int col = (tmpY/3)*3;
		
		for(int i = row;i<row+3;i++) {
			for(int j = col; j<col+3; j++) {
				if(board[i][j] == num) return false;
			}
		}
		
		//세가지 경우에 대해 모두 안전하다면 return
		return true;
	}

}

check

• 주의할 점은 스도쿠의 정답이 여러 개일 수도 있다는 것이다. 그래서 스도쿠 정답을 찾으면 바로 출력해주고 함수를 강제종료한다.

• 처음에 시간초과가 나왔는데 스도쿠 함수 sudoku를 부를 때 마다 BufferedWriter 객체를 계속 선언하기 때문이었다. 이렇게 반복적으로 선언해야할 때는 static으로 선언을 먼저 해주도록 하자.

• N-Queen과 비슷한 백트래킹 문제였다. 따라서 N_Queen과 비슷하게 재귀함수 하나, 유효성 검사 함수 하나를 생성해주었다.

• 백트래킹에서 중요한 점은 다시 빈칸의 상태로 만들어 주는 것이다. 백트래킹이 익숙하지 않아 초반에 이 사실을 간과하였다.