[BOJ] 2580 스도쿠 - JAVA

1. 문제

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

2580번: 스도쿠

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

---

2. 풀이

메인 함수

스도쿠 판에 값을 저장하면서 0이 등장하면 zero 리스트에 위치를 저장한다.

static int[][] sudoku = new int[9][9];
static ArrayList<int[]> zero = new ArrayList<>();
static StringBuilder sb = new StringBuilder();

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st;
   for (int i = 0; i < 9; i++) {
      st = new StringTokenizer(in.readLine());
      for (int j = 0; j < 9; j++) {
         sudoku[i][j] = Integer.parseInt(st.nextToken());
         if (sudoku[i][j] == 0) zero.add(new int[]{i, j});
      }
   }

   solve(0);

   System.out.print(sb);
}

 

입력받은 위치 값이 가능한지 체크하는 메서드

• i,j값을 입력받고 가로, 세로, 3*3칸 중 자신과 동일한 값이 있는지 체크한다.
• 위의 조건을 모두 통과했다면 해당 칸이 가능하다는 의미로 true를 리턴한다.

private static boolean isAvailable(int i, int j) {
   int now = sudoku[i][j];
   for (int k = 0; k < 9; k++) {
      if (k != j && now == sudoku[i][k]) return false;
      if (k != i && now == sudoku[k][j]) return false;
   }

   for (int fi = (i / 3) * 3, k = fi; k < fi + 3; k++) {
      for (int fj = (j / 3) * 3, l = fj; l < fj + 3; l++) {
         if(k==i && l==j) continue;
         if (now == sudoku[k][l]) return false;
      }
   }

   return true;
}

 

탐색 메서드

• 기저조건 : cnt==0의 개수라면 지금까지 저장된 스도쿠판을 static StringBuilder에 저장하고 true를 반환한다.
• 유도조건
  • 1부터 9까지 반복하며 일단 0자리에 값을 넣는다. 넣은 값이 가능하고, 그 다음 재귀호출이 true를 반환했다면 더 이상 탐색할 필요없는 것이므로 같이 true를 반환하고 끝낸다.
  • 끝내지 못했다면 i를 넣은 값을 0으로 되돌린다. (지금 생각해보니 굳이 되돌릴 필요 없을 것 같다. 어차피 다시 덮어씌워지니까)

private static boolean solve(int cnt) {
   if (cnt == zero.size()) {
      for (int i = 0; i < 9; i++) {
         for (int j = 0; j < 9; j++) {
            sb.append(sudoku[i][j]).append(" ");
         }
         sb.append("\n");
      }
      return true;
   }

   for (int i = 1; i <= 9; i++) {
      sudoku[zero.get(cnt)[0]][zero.get(cnt)[1]] = i;
      if (isAvailable(zero.get(cnt)[0], zero.get(cnt)[1]) && solve(cnt + 1)) return true;
      sudoku[zero.get(cnt)[0]][zero.get(cnt)[1]] = 0;
   }

   return false;
}

---

3. 결과