[SWEA] 1974번: 스도쿠 검증 (Java)

SWEA #1974번 : 스도쿠 검증

 

스도쿠는 숫자퍼즐로, 가로 9칸 세로 9칸으로 이루어져 있는 표에 1 부터 9 까지의 숫자를 채워넣는 퍼즐이다.
 

같은 줄에 1 에서 9 까지의 숫자를 한번씩만 넣고, 3 x 3 크기의 작은 격자 또한, 1 에서 9 까지의 숫자가 겹치지 않아야 한다.
 

입력으로 9 X 9 크기의 스도쿠 퍼즐의 숫자들이 주어졌을 때, 위와 같이 겹치는 숫자가 없을 경우, 1을 정답으로 출력하고 그렇지 않을 경우 0 을 출력한다.


[제약 사항]

1. 퍼즐은 모두 숫자로 채워진 상태로 주어진다.

2. 입력으로 주어지는 퍼즐의 모든 숫자는 1 이상 9 이하의 정수이다.


[입력]

입력은 첫 줄에 총 테스트 케이스의 개수 T가 온다.

다음 줄부터 각 테스트 케이스가 주어진다.

테스트 케이스는 9 x 9 크기의 퍼즐의 데이터이다.


[출력]

테스트 케이스 t에 대한 결과는 “#t”을 찍고, 한 칸 띄고, 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

 

소스 코드 1.   사용 여부로 판단

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_D2_1974_스도쿠검증 {
	
	static int[][] map;
	static int[] num;
	static boolean[] isUsed;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());	// 테스트케이스 수
		for(int t=1; t<=T; t++) {
			map = new int[9][9];	
			
			for(int i=0; i<9; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<9; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());	// 입력받아 표에 저장.
				}
			}
			
			sb.append("#"+t+" ").append(solving()).append("\n");
		}
		System.out.println(sb);

	}
	
	public static int solving() {	// 수평, 수직, 네모에 겹치는 숫자가 없는지 체크
		// horizontal 수평체크
		for(int i=0; i<9; i++) {
			num = new int[10];
			isUsed = new boolean[10];	// 배열에 저장된 숫자가 사용되었는지 여부를 저장하는 배열.
			
			for(int j=0; j<9; j++) {
				if(isUsed[map[i][j]]) {		// 겹치는 숫자가 있다면 0 반환
					return 0;
				}
				isUsed[map[i][j]] = true;	// 겹치는 숫자가 없다면 현재 숫자를 사용한 것으로 저장
			}
		}
		// vertival 수직체크
		for(int i=0; i<9; i++) {
			num = new int[10];
			isUsed = new boolean[10];
			
			for(int j=0; j<9; j++) {
				if(isUsed[map[j][i]]) {
					return 0;
				}
				isUsed[map[j][i]] = true;
			}
		}
		// squre 네모체크
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				
				isUsed = new boolean[10];
				for(int r=0; r<3; r++) {
					for(int c=0; c<3; c++) {
						if(isUsed[map[i*3+r][j*3+c]]) {  // 인덱스 0, 3, 6 이 첫칸인 행/열을 탐색
							return 0;
						}
						isUsed[map[i*3+r][j*3+c]] = true;
					}
				}
			}
		}
		return 1;	// 겹치는 숫자가 없다면 1 반환
	}
}

 

실행 결과

 

 

소스 코드 2.   합을 이용

package sol;

import java.util.Scanner;

public class Solution_D2_1974_스도쿠검증3 {
	
  static int[][] sudokuMap;
  static int answer;
  
  public static void main(String[] args) {
	 Scanner sc = new Scanner(System.in);
	 int T = sc.nextInt();
	 
	 for(int tc=1; tc<=T; tc++) {
	   //테스트케이스 마다 초기화
	   sudokuMap = new int[9][9];	 
		 
	   //데이터 입력
	   for(int i=0; i<9; i++) {
		  for(int j=0; j<9; j++) {
	         sudokuMap[i][j]=sc.nextInt();		  
		  }		  
	   }
	   
	   int checkSum1, checkSum2;
	   answer=1;
	   
	   //가로 검사, 세로 검사
	   for(int i=0; i<9; i++) {
		  checkSum1=0;
		  checkSum2=0;
		  for(int j=0; j<9; j++) {
		    checkSum1+=sudokuMap[i][j];
		    checkSum2+=sudokuMap[j][i];
		  }
		  if(checkSum1!=45||checkSum2!=45) {
			  answer=0;
			  break;
		  }
	   }
	   
	   //작은 사각형 검사
       for(int i=0; i<=6; i+=3) {
		   for(int j=0; j<=6; j+=3) {
			   smallSquare(i, j);
		   }
	   }
	   
	   System.out.println("#"+tc+" "+answer);
	 }
	 sc.close();
  }//main
  
  static void smallSquare(int r, int c) {
	  int checkSum=0;
	  for(int i=r; i<r+3; i++) {
		   for(int j=c; j<c+3; j++) {
			   checkSum += sudokuMap[i][j];
		   }
	   }
	  if(checkSum != 45) answer=0;
  }
}

 

 

 

소스 코드 3.  HashSet 사용

package sol;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Solution_D2_1974_스도쿠검증4 {
  
  static int [][]sudokuMap = new int[9][9];
  static int validNum;

  public static void main(String[] args){
	   
      Scanner sc = new Scanner(System.in);
      int T = sc.nextInt();         
      Set<Integer> set = new HashSet<Integer>();//중복 데이터를 제거할 목적으로 사용
      
      for(int tc=1; tc<=T; tc++) {    
    	  
    	  //데이터 입력
          for(int i=0; i<9; i++) {
             for(int j=0; j<9; j++) {
            	 sudokuMap[i][j]= sc.nextInt();
             }
          }       
          
          validNum=1;//유효한 숫자 1을 기본값으로 하고 유효하지 못했을때 0으로 변경
         
          //9개의 가로행 검사!!
          for(int i=0; i<9; i++) {
             for(int j=0; j<9; j++) {//한개의 행에 대해 set에 저장
                  set.add(sudokuMap[i][j]);
             }
             if(set.size()!=9) {//겹치는 숫자가 발생시 
                 validNum=0;  //유효하지 못한 숫자라고 판단
                 break;
             }
             set.clear();
          }
          
          if(validNum==1)//가로행의 검사가 유효했을때
          for(int j=0; j<9; j++) {  //9개의 세로행 검사!!
            for(int i=0; i<9; i++) {
                  set.add(sudokuMap[i][j]);
              }
              if(set.size()!=9) {//겹치는 숫자가 발생시 
                  validNum=0;   //유효하지 못한 숫자라고 판단
                  break;
              }
              set.clear();
          }

   	   //작은 사각형 9개 검사
         for(int i=0; i<=6; i+=3) {
   		   for(int j=0; j<=6; j+=3) {
   			   smallSquare(i, j);
   		   }
   	     }
          
        System.out.println("#"+tc+" "+validNum);        
      }
      sc.close();
   }//main
   
   static void smallSquare(int r, int c) {
		  int checkSum=0;
		  for(int i=r; i<r+3; i++) {
			   for(int j=c; j<c+3; j++) {
				   checkSum += sudokuMap[i][j];
			   }
		   }
		  if(checkSum != 45) validNum=0;
   }
}

실행 결과

 

중복 데이터를 제거할 목적으로 Set API를 사용한다.

 

Set은 데이터를 중복해서 저장할 수 없고, 저장 순서가 보장되지 않는다.

1. HashSet : 데이터를 중복 저장할 수 없고, 순서를 보장하지 않는다.

2. TreeSet : 중복된 데이터를 저장할 수 없고 입력한 순서대로 값을 저장하지 않는다.

                        차이점은 TreeSet은 기본적으로 오름차순으로 데이터를 정렬한다.

3. LinkedHashSet : 중복된 데이터를 저장할 수 없다. 차이점은 입력된 순서대로 데이터를 관리한다.

 

 

Set<Integer> set = new HashSet<Integer>();//중복 데이터를 제거할 목적으로 사용

//9개의 가로행 검사!!
  for(int i=0; i<9; i++) {
     for(int j=0; j<9; j++) {//한개의 행에 대해 set에 저장
          set.add(sudokuMap[i][j]);
     }
     if(set.size()!=9) {//겹치는 숫자가 발생시 
         validNum=0;  //유효하지 못한 숫자라고 판단
         break;
     }
     set.clear();
  }

1~9까지의 숫자가 들어가게 되면 set의 사이즈가 9가 되어야 하는데,

겹치는 숫자가 발생 시 중복된 기존의 값을 덮어씌우기 때문에 set의 사이즈가 9보다 작아진다.