[BOJ/백준 - 2580] 스도쿠

문제 출처: https://www.acmicpc.net/problem/2580

2580번: 스도쿠

---

	public class BOJ_2580 {
	static int[][] arr; // 스도쿠판
	static ArrayList<Vertex> al; // 0의 좌표를 가지는 리스트
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	arr = new int[9][9];
	al = new ArrayList<>();
	for(int i=0; i<9; i++){
	st = new StringTokenizer(br.readLine());
	for(int j=0; j<9; j++){
	arr[i][j] = Integer.parseInt(st.nextToken());
	if(arr[i][j] == 0){
	al.add(new Vertex(i, j)); // 입력받으면서 0이 들어오면 해당 좌표값을 리스트에 보관
	}
	}
	}
	backtracking(0); // 백트래킹은 0값의 좌표를 보관하고 있는 리스트를 기준으로 한다
	}
	private static void backtracking(int depth){
	// depth가 리스트의 크기만큼 왔다면 > 마지막 좌표까지 성공적으로 탐색했음 > 출력 후 종료
	if(depth == al.size()){
	printArr();
	System.exit(0);
	}
	Vertex v = al.get(depth);
	int ix = v.x;
	int iy = v.y;
	for(int i=1; i<=9; i++){
	// 반복문은 1부터 9까지 돌면서 해당 좌표에 값이 들어갈 수 있는지 없는지 검사사
	if(isPossible(ix, iy, i)){
	arr[ix][iy] = i;
	backtracking(depth+1);
	arr[ix][iy] = 0;
	}
	}
	}
	// 스도쿠 규칙을 적용해 해당 좌표의 숫자가 들어갈 수 있는지 없는지 검사
	private static boolean isPossible(int x, int y, int v){
	for(int i=0; i<9; i++){
	if(arr[x][i] == v){ // 가로값 검사
	return false;
	}
	if(arr[i][y] == v){ // 세로값 검사
	return false;
	}
	}
	// 사각형 검사
	int startSero;
	int startGaro;
	if(x<=2){
	startSero = 0;
	}else if(x<=5){
	startSero = 3;
	}else{
	startSero = 6;
	}
	if(y<=2){
	startGaro = 0;
	}else if(y<=5){
	startGaro = 3;
	}else{
	startGaro = 6;
	}
	for(int i=startSero; i<=startSero+2; i++){
	for(int j=startGaro; j<=startGaro+2; j++){
	if(arr[i][j] == v){
	return false;
	}
	}
	}
	return true;
	}
	private static void printArr(){
	for(int i=0; i<9; i++){
	for(int j=0; j<9; j++){
	System.out.print(arr[i][j]+" ");
	}
	System.out.println();
	}
	}
	}
	// 0 좌표 표시용 클래스
	class Vertex{
	int x;
	int y;
	public Vertex(int x, int y){
	this.x = x;
	this.y = y;
	}
	}

view raw BOJ_2580.java hosted with ❤ by GitHub

---

코드의 설명은 주석으로 했음

기본적인 백트래킹 문제를 푸는 방법에 벗어나지 않는 문제였다.

아 그리고 이건 가능한 값이 여러개여도 하나만 출력하면 되기때문에,

종료조건에 걸리면 답을 출력하고 System.exit(0);로 종료하면 된다

 

이 문제로 백준 단계별로 풀어보기 백트래킹 다 풀었다 (현시점 기준. 문제는 계속 추가되는거같음)

나는 성공률보고나서

N과M 시리즈 -> N-Queen -> 연산자 끼워넣기 -> 스타트와 링크를 풀고 마지막으로 이문제를 풀었는데

아마 N과 M시리즈를 풀면서 머릿속에 백트래킹 문제에 대한 해결법이 이해가 되었다면 해당 문제도 성공률에 쫄지말고 풀 수 있을거라 생각됨

 

예전에 취업준비 할때는 백트래킹을 풀면서도 어떻게 구조를 잡아야 하는지에 대한 이해가 잘 안되어서

계속 남의 코드를 봤었는데,

이번에는 N과 M시리즈를 풀면서 대충 감이 오더니 구조가 감이 잡혀서 풀 수 있게 되었다.

 

어려운 문제는 어렵겠지만 단계별 풀어보기는 그냥 N과 M + 조건식 추가 정도 느낌이였던거 같았음

사람이 하면 늘긴 느나보다