[java]스도쿠 검증 - SWEA 1974

풀이

문제 해석을 하자면,

• 실제 스도쿠 게임처럼 숫자가 중복되지 않고 잘 성립하는지 묻는 문제이다.

풀이

• 2가지를 진행하자
  • 완전탐색으로 전체 9*9 가로,세로 확인
  • 각각 3*3 사각형 전체 확인
• 참, 거짓 판단하는 시점만 잘 신경써주자
• 특히, countVisit 배열에 1~9 숫자 조회 횟수를 기록하여 해결한다.

코드

import java.io.*;
import java.util.*;
public class 스도쿠검증_1974 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int T = Integer.parseInt(br.readLine());
    for(int t=1; t<=T; t++) {
      //input
      int N=9;
      int[][] inArr = new int[N][N]; // 매번 새로 할당
      for(int i=0; i<N; i++) {
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++) {
          inArr[i][j] = Integer.parseInt(stk.nextToken());
        }
      }
      //run
      int result = 1;
      // 1. 9x9 가로,세로
      int[] countVisit = new int[N+1]; //init
      for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
          // 가로와 세로 한번에 확인하기
          countVisit[inArr[i][j]]++;
          countVisit[inArr[j][i]]++;
        }
        // 가로세로 참,거짓 판단
        for(int k=1; k<=N; k++) {
          if(countVisit[k] != 2*(i+1)) {
            result = 0; // false
          }
        }
      }
      // 2. 3x3사각형
      if(result == 1) {
        countVisit = new int[N+1]; //init
        int cx=0; int cy=0; int idx=1;
        while(true) {
          if(cy>=9) {
            cx+=3; cy=0;
            if(cx>=9) break; // 탈출 시점
          }
          for (int i = cx; i < cx+3; i++) {
            for (int j = cy; j < cy+3; j++) {
              countVisit[inArr[i][j]]++;
            }
          }
          // 3x3사각형 참,거짓 판단
          for(int k=1; k<=N; k++) {
            if(countVisit[k] != idx) {
              result = 0; // false
            }
          }
          idx++;
          cy+=3; // update
        }
      }
      //output
      sb.append("#"+t+" "+result+"\n");
    }
    System.out.print(sb);
  }
}

느낀점

생략