[백준] 단계별로 풀어보기(단계:14,백트래킹,JAVA)2580번, 스도쿠

문제 링크

2580번: 스도쿠

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

백트래킹이란 깊이 우선 탐색을 바탕으로 탐색 중 오답을 만나면 이전 분기점으로 돌아가서 다른 해결방법이 있는지 확인하고 더 이상 없으면 더 이전에 분기점으로 돌아가서 해결방법을 찾아보는 방식입니다.깊이 우선 탐색은 모든 경우의 수를 검색하게 되지만 백트래킹은 오답으로 판단될시 그에 해당하는 자식 노드들은 모두 무시하고 넘어가기 때문에 더욱 효율적으로 코드가 진행됩니다.

검은색 : 실행되지 않은 노드

빨간색 : 오답으로 판단한 노드

초록색 : 올바른 값이라고 판단한 노드

위에 그림처럼 부모노드가 틀리다고 판정되면 자식노드 무시하고 이전 분기점으로 돌아가서 확인하는 방식으로 코드가 전개되어 가는 방식입니다.

 

스도쿠는 기본적 규칙은 문제에 대한 설명과 동일합니다.

스도쿠가 완성되기에 경우의 수를 확인하는 것이기 때문에 (0,0)을 기준으로 백트래킹을 시작하였습니다.

0은 빈 공간을 표현하는 숫자여서 0일 때 들어갈 수 있는 경우의 수를 numCheck함수를 찾도록 하였습니다.numCheck는 가로줄 확인(rowCheck)와 세로줄 확인(colCheck)와 블럭 확인(blockCheck)로 확인하도록 하였습니다.틀린 경우의 수에 만났을 경우 이전 노드로 돌아가서 다른 경우의 수를 입력하도록 하였습니다.스도쿠 판으로 설명하겠습니다.

 

(0,0)에서 시작해서 빈 공간을 0이라 했을 때 numCheck를 통해 들어갈 수 있는 경우의 수를 찾아서 넣습니다.

(0,1)이 0이었어서 numCheck를 한 결과 1~9까지 숫자 중 9가 들어갈 수 있다고 판정되어 9가 들어갔습니다.

(0,3)이 0이었어서 numCheck를 한 결과 1~9까지 숫자중 7,8이 들어갈 수 있다고 판정되어  작은 수 7이 들어갔습니다.

(0,6)이 0이었어서 numCheck를 한 결과 1~9까지 숫자중 4가 들어갈 수 있다고 판정되어 4가 들어갔습니다.

(0,7)이 0이었어서 numCheck를 한 결과 1~9까지 숫자중 1,8이 들어갈 수 있다고 판정되어  작은 수 1이 들어갔습니다.

(0,8)이 0이었어서 numCheck를 한 결과 1~9까지 숫자중 아무것도 들어가지 못하여 ?로 처리했으며 이전 노드로 돌아갑니다.

(0,7)이 0이었어서 numCheck를 한 결과 1~9까지 숫자중 1,8이 들어갈 수 있다고 판정되었지만 1이 들어갔을 때 오답으로 판정되었으므로 이번에는 8이 들어가게 됩니다.

(0,7)이 0이었어서 numCheck를 한 결과 1~9까지 숫자중 1이 들어갈 수 있다고 판정되어  1이 들어갔습니다.

이후 행이 바뀌고 다시 백트래킹을 반복하여 정답인 경우의 수를 찾는 과정을 반복하여 결과를 도출하는 알고리즘으로 작성하였습니다.

 

• 스도쿠 판 숫자를 저장할 배열 sudoku을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• sudoku를 해결하는 함수 sudokuSolution을 만들었습니다.
• 빈 칸에 들어갈 수 있는 숫자를 확인하는 함수 numCheck를 만들었습니다.

• 가로열을 확인하는 함수 : rowCheck
• 세로열을 확인하는 함수 : colCheck
• 3x3블럭을 확인하는 함수  : blockCheck

• 스도쿠를 완성하면 System.out.println()을 사용하여 StringBuilder를 출력하였습니다
• 위에 알고리즘을 토대로 sudokuSolution을 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[][] sudoku = new int[9][9];	//스도쿠 판 배열
	static StringBuilder sb = new StringBuilder();	//결과 출력 StringBuilder
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	StringTokenizer st;
        //스도쿠 값 배열에 저장
    	for(int i=0;i<9;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		for(int j=0;j<9;j++) {
    			sudoku[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
        //스도쿠 문제 풀이 함수 실행
    	sudokuSolution(0,0);
    	br.close();
	}
    //--------------------스도쿠 문제 풀이 함수------------------
	public static void sudokuSolution(int x, int y) {
		if(y==9){		//행 바꿀때
			sudokuSolution(x+1, 0);
			return;
		}
        //-----------행이 9이면 모든 스도쿠 숫자 삽입 완료!-------------
        //-----------완료 되었으니 StringBuilder를 통해 결과 출력-------
		if(x==9) {		
	    	for(int i=0;i<9;i++) {
	    		for(int j=0;j<9;j++) {
	    			sb.append(sudoku[i][j] + " ");
	    		}
	    		sb.append("\n");
	    	}
	    	System.out.print(sb);
	    	System.exit(0);
		}
        //--------------백 트래킹을 통해 스도쿠 숫자 찾기-----------
		if(sudoku[x][y]==0) {
			for(int i=1;i<=9;i++) {
				if(numCheck(x,y,i)) {
					sudoku[x][y]=i;
					sudokuSolution(x, y+1);
				}
			}
            //------안되는 경우의 수일 경우 이전 노드에서 초기화-------
			sudoku[x][y]=0;
			return;
		}
		sudokuSolution(x, y+1);
	}
    //-------------스도쿠 숫자 들어갈 수 있는지 확인 함수 ----------
	public static boolean numCheck(int x,int y, int num) {
		if(rowCheck(x,num))
			return false;
		else if(colCheck(y,num))
			return false;
		else if(blockCheck(x, y,num))
			return false;
		else
			return true;
	}
    //------------가로줄 체크------------
	public static boolean rowCheck(int x,int num) {
		for(int i=0;i<9;i++) {
			if(sudoku[x][i]==num)
				return true;
		}
		return false;
	}
    //-----------세로줄 체크--------------
	public static boolean colCheck(int y,int num) {
		for(int i=0;i<9;i++) {
			if(sudoku[i][y]==num)
					return true;
		}
		return false;
	}
    //-----------3x3 블럭 체크--------------
	public static boolean blockCheck(int x, int y, int num) {
		int start_x = (x/3)*3, end_x = start_x+3;
		int start_y = (y/3)*3, end_y = start_y+3;
		for(int i=start_x;i<end_x;i++) {
			for(int j=start_y;j<end_y;j++) {
				if(sudoku[i][j]==num)
					return true;
			}
		}
		return false;
	}
}