[백준] 2580번 : 스도쿠 (JAVA)

저번 N-Queen문제에 이어서 다음 문제인 스도쿠를 풀었다.

N-Queen 문제와 유형이 비슷해서 그나마 수월하진 않지만 풀 수 있었다!

 

 

백트래킹에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/3

알고리즘 - 백트래킹(Backtracking)

 

 

바로 앞 문제인 9663번 : N-Queen에 대한 내용은 바로 앞의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/9

[백준] 9663번 : N-Queen (JAVA)

 

---

<문제>

 

<문제 해석>

백트래킹을 이용하여 스도쿠의 0인 부분을 알맞은 숫자로 채워넣어라.

 

 

<문제 해결>

앞의 문제인 N-Queen과 비슷한 문제이다.

N-Queen은 상하좌우, 대각선이 예외였지만,

 

스도쿠는 같은 행, 열 , 3x3 안의 정사각형 안에 겹치는 숫자가 없어야한다.

 

 

<알고리즘>

1. 입력받은 스도쿠를  2차원 배열에 넣는다.

2. for문을 이용해 스도쿠에서 0을 찾게되면,

3. 같은 행, 같은 열, 3x3 정사각형에 중복되지 않는 숫자를 집어넣고,

4. 다음 0을 찾는다.

5. 1,2,3,4 단계를 반복한다.

6. 행이 마지막 행이면 수열을 출력하고 종료한다.

 

 

<코드>

import java.io.IOException;
import java.util.Scanner;

class Main{

	static int[][] ar = new int[9][9];
    public static void main(String[] args) throws NumberFormatException, IOException {
    	Scanner sc = new Scanner(System.in);
    
    	for(int i=0;i<9;i++) {
    		for(int j=0;j<9;j++) {
    			ar[i][j] = sc.nextInt();
    		}
    	}
    	
    	play(0,0);
    }
    
    //빈칸 찾기 -> 게임 진행
    static void play(int row,int col) {
    	
    	if(col == 9) {
    		play(row+1,0);
            return;
    	}
    	
    	if(row ==9) {
    		for(int i=0;i<9;i++) {
    			for(int j=0;j<9;j++) {
    				System.out.print(ar[i][j]+" ");
    			}
    			System.out.println();
    		}
    		
    		System.exit(0);
    	}
    	
    	if(ar[row][col] == 0) {
    		for(int i=1;i<=9;i++) {
    			if(check(row,col,i)) {
    				ar[row][col] = i;
    				play(row,col+1);
    			}
    		}
    		
    		ar[row][col] = 0;
    		return;
    	}
    	
    	play(row,col+1);
    }
    
    static boolean check(int i,int j,int value) {
    	
    	int set_row = (i/3)*3;
    	int set_col = (j/3)*3;
    	
    	//같은 행, 같은 열
    	for(int a=0;a<9;a++) {
    		if(ar[i][a] == value)	{
    			return false;
    		}
    		if(ar[a][j] == value) {
    			return false;
    		}
    	}
    	
    	//3x3
    	for(int x=set_row;x<set_row+3;x++) {
    		for(int y=set_col;y<set_col+3;y++) {
    			if(ar[x][y] == value) {
    				return false;
    			}
    		}
    	}
    	return true;
    }

}

 

---

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

2580번: 스도쿠