[백준] 2239 스도쿠 - 백트래킹(Backtracking) + DFS(깊이우선탐색) + 조합(Combination) + 순열(Permutation) JAVA

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

2239번: 스도쿠

코드설명

DFS(깊이우선탐색) + 브루트포스(bruteforce) + 조합(Combination) 을 활용하는 문제입니다.

 

문제로직은 2가지로 나뉩니다.

1. simulate 함수는 백트래킹을 이용해 스도쿠를 풀어나가는 함수입니다. 이 함수는 현재 위치 (r, c)에서 가능한 숫자를 시도하고, 가능한 경우 재귀적으로 다음 칸으로 진행합니다.
   • 만약 현재 위치에 이미 숫자가 채워져 있다면 해당 숫자를 놓고 다음 칸으로 이동합니다.
   • 현재 위치에 숫자가 채워져 있지 않다면 1부터 9까지의 숫자를 시도하면서 가능한 경우에 대해 재귀 호출을 합니다.
2. availableCheck 함수는 현재 위치에 특정 숫자를 놓을 수 있는지 여부를 검사하는 함수입니다. 행, 열, 그리고 작은 3x3 격자를 검사하여 중복된 숫자가 없는지 확인합니다.
   • 행과 열을 검사하여 중복된 숫자가 있는지 확인합니다.
   • 3x3 작은 격자를 검사하여 중복된 숫자가 있는지 확인합니다. 격자의 시작 위치를 (r / 3) * 3 ~ (r / 3) * 3 + 3, (c / 3) * 3 ~ (c / 3) * 3  + 3로 계산하여 해당 부분을 검사합니다.

문제에서 현재 위치에 특정숫자를 둘때, 행과 열을 확인하는 부분은 쉽지만, 3x3 으로 나누어서 처리하는 부분에서 놓쳤었던 점이 있습니다.

아래에서 i < newR * 3 + 3 에서 처음에는 단순히 i < newR + 3 으로 하여 3x3 사각형에서 올바르게 스도쿠를 두지 못해서 틀렸습니다. 

i의 범위를 올바르게 i = newR * 3; i < newR * 3 + 3 으로 처리해야만 합니다.

//시작칸의 3x3 을 구하기 위해.
int newR = r / 3;
int newC = c / 3;
for(int i=newR * 3; i < newR * 3  + 3; i++) {
    for(int j=newC * 3; j < newC * 3 + 3; j++) {
        if(map[i][j] == num) {
            return false;
        }
    }
}

 

제출 시 틀린다면, 아래의 입력으로 테스트해보는 것을 추천드립니다.

입력 
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
 
출력
123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    public static int N, M, K, H;
    public static int[][] map = new int[9][9];
    public static int idx = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        StringTokenizer st = new StringTokenizer(br.readLine());
        
        
        for (int i = 0; i < 9; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	String str = st.nextToken();
			for (int j = 0; j < 9; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
        
        simulate(0, 0, 0);
        
        
    }
    
    public static void simulate(int level, int r, int c) {
    	if( c >= 9 ) {
    		r = r + 1;
    		c = 0;
    	}
    	if(level >= 9 * 9 ) {
    		for(int i=0;i<9;i++) {
    			for(int j=0;j<9;j++) {
    				System.out.print(map[i][j]);
    			}
    			System.out.println();
    		}
    		System.exit(0);
    		return ;
    	}
    	
    	if(r >= 9) return ;
    	
    	if(map[r][c] == 0) {
    		for(int i=1;i<10;i++) {
    			map[r][c] = i;
    			if(availableCheck(r, c, map[r][c]) == true) {
    				simulate(level + 1, r, c + 1);	
    			}
    			map[r][c] = 0;
    		}
    	}else { //0이 아닐경우에만 아무것도 안하고 넘어가야합니다. 처음에 무조건 넘어가도록 하여 0이 아닌경우가 가장 먼저 나왔습니다. 이러한 점들을 유의합니다.
    		simulate(level + 1, r, c + 1); // 아예 선택하지 않는경우에도 계속됩니다.	
    	}
    	
    	
    }
    
    
    
    public static boolean availableCheck(int r, int c, int targetNum) {
    	
    	//행 검사.
    	for(int i=0;i<9;i++) {
    		if(i == r && c == c ) continue;
    		if(map[i][c] == targetNum) return false;
    	}
    	
    	//열 검사
    	for(int i=0;i<9;i++) {
    		if(r == r && i == c ) continue;
    		if(map[r][i] == targetNum) return false;
    	}
    	
    	//해당 칸을 검사.
    	//9개의 칸으로 생각할 수 있습니다.
    	// ( 0 ~ (r / 3) * 3 , 0 ~ ( c / 3) * 3)   { (r/3)  ~ ( r / 3 )  , 3 ~ (c/3) * 3) ( 0 ~ ( r / 3 ), 6 ~ ( c / 3 ) * 3}  
    	// ( 1 ~ (r / 3) * 3 , 0 ~ ( c / 3) * 3 ) 
    	//
    	for(int i=(r / 3) * 3; i<(r / 3) * 3 + 3; i++) {
    		for(int j=( c / 3 ) * 3; j < ( c/ 3 ) * 3 + 3; j++) {
    			if(r == i && c == j) continue;
    			if(map[i][j] == targetNum) {
    				return false;
    			}
    		}
    	}
    	return true;
    }
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[][] map;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		map = new int[9][9];
		for(int i=0;i<9;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String inputLine = st.nextToken();
			for(int j=0;j<9;j++) {
				map[i][j] = inputLine.charAt(j) - '0';
			}
		}
		
		simulate(0, 0, 0);
	}
	
	public static void simulate(int level, int r, int c) {
		if( c >= 9 ) {
			r = r + 1;
			c = 0;
		}
		if(level >= 9*9) {
			//찾은경우입니다.
			for(int i=0;i<9;i++) {
				for(int j=0;j<9;j++) {
					System.out.print(map[i][j]);
				}
				System.out.println();
			}
			System.exit(0);
			return ;
		}
		
		if( r >= 9) {
			
			return ;
		}
		
		//만약 0 이라면, 
		if(map[r][c] == 0) {
			for(int num = 1; num <= 9; num++) {
				//행, 열, 3x3 에 해당 숫자가 존재하지 않을경우에만 넣어야할 것 입니다.
				if ( checkSudoku(num, r, c) == true ) {
					map[r][c] = num;
					simulate(level + 1, r, c + 1);
				}
			}
			map[r][c] = 0;
		}
		
		//만약 0 이 아닐경우에만 담은칸으로 그냥 넘어가도록 해야합니다.
		else if(map[r][c] != 0) {
			//아무것도 하지 않고 넘어가는 경우입니다.
			simulate(level + 1, r, c + 1);	
		}
		
	}
	
	public static boolean checkSudoku(int num, int r, int c) {
		
		for(int col = 0; col < 9; col++) {
			if(map[r][col] == num) {
				return false;
			}
		}
		
		for(int row = 0; row < 9; row++) {
			if(map[row][c] == num) {
				return false;
			}
		}
		
		//시작칸의 3x3 을 구하기 위해.
		int newR = r / 3;
		int newC = c / 3;
		for(int i=newR * 3; i < newR * 3  + 3; i++) {
			for(int j=newC * 3; j < newC * 3 + 3; j++) {
				if(map[i][j] == num) {
					return false;
				}
			}
		}
		
		return true;
	}
	
}