백준 스도쿠

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

2580번: 스도쿠

백트 문제이긴한데 ㅡㅡ 그닥 문제 설명이 부족하지 않나 생각이 들정도로 어려운 문제였습니다.

개인적으론 골드3정도 줘도 되는 문제같네요 .... 너무 어렵네요.

 

맨아래 정답이 잇습니다.

 

풀이과정: 

먼저 기본적이 아이디어는 

1. row,col, 3x3 box를 체크해줍니다. 그

체크함수를 만들어줫는데

 

check( i,j,num )

체크함수 

public static boolean check(int i, int j, int number) {
		return !isRow(i,number)&&!isBox(i,j,number) && !isCol(j, number);
	}

즉 여기서 row,colum,3x3 box안에도 숫자 num이 없으면 모두 존재하지않다면 이 특정 num값이 스도쿠에 들어가는 게 가능하게 됩니다., ㅡㅡ 솔직히 이거 떠올리면 다 푼겁니다.

 

2.체크가 끝난 친구는  백트래킹을 쓰면서  순환해주면 끝입니다.

	public static boolean backtracking() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if( maps[i][j]==0 ) {
					for( int num=1;num<=n;num++ ) {
						if( check( i,j,num ) == true ) {
							maps[i][j]=num;
							
							
							if( backtracking() == true ) {
								return true;
							}else {
								maps[i][j]=0;
							}
						}
					}
					return false;
				}
				
			}
		}
		
		return true;
	}

 

정답:

import java.util.*;

import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;
public class Main {
	public static int n=9;
	public static int [][]maps=new int[n][n];
	
	private static boolean isBox(int row, int col, int number) {
        int r = row - row % 3;
        int c = col - col % 3;

        for (int i = r; i < r + 3; i++) {
            for (int j = c; j < c + 3; j++) {
                if (maps[i][j] == number) {
                    return true;
                }
            }
        }
        return false;
    }
	
	public static boolean isRow(int r,int num) {
		for(int i=0;i<9;i++) {
			 if(maps[r][i]==num) {
				 return true;
			 }
		}
		return false;
	}
	 private static boolean isCol(int col, int number) {
	        for (int i = 0; i < n; i++) {
	            if (maps[i][col] == number) {
	                return true;
	            }
	        }
	        return false;
	    }
	public static boolean check(int i, int j, int number) {
		return !isRow(i,number)&&!isBox(i,j,number) && !isCol(j, number);
	}
	
	
	public static boolean backtracking() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if( maps[i][j]==0 ) {
					for( int num=1;num<=n;num++ ) {
						if( check( i,j,num ) == true ) {
							maps[i][j]=num;
							
							
							if( backtracking() == true ) {
								return true;
							}else {
								maps[i][j]=0;
							}
						}
					}
					return false;
				}
				
			}
		}
		
		return true;
	}
	
	public static void main(String[] args) throws Exception {
		Scanner scan =new Scanner(System.in);
        //스도쿠는 18세기 스위스 수학자가 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 
		//현재 많은 인기를 누리고 있다
		//게임은 아래 그림과 같이 가로,세로 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판위에서 
		//1~9까지이의 숫자 중 하나가 쓰여잇다.
		
		//1 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한번씩만 나타나야 한다.
		//2 굵은 선으로 구분되는 잇는 3x3 안에서는 1부터 9까지 한번씩 나타나야한다
		
	    
	    for(int i=0;i<n;i++) {
	    	for(int j=0;j<n;j++) 
	    	{
	    		maps[i][j]=scan.nextInt();
	    	}
	    }
	    if(backtracking()==true) {
	    	for(int i=0;i<n;i++) {
	    		for(int j=0;j<n;j++) {
	    			System.out.print(maps[i][j]+" ");
	    		}
	    		System.out.println();
	    	}
	    }	
	}
}