BOJ) 스도쿠 (2580 번)

스도쿠

2580번: 스도쿠

스도쿠의 조건에 따라 로직을 짜주었고, 백트래킹을 이용했다.

(백트래킹을 사용하지 않으면 시간초과가 난다)

우선, 재귀 함수를 사용할 예정이어서 모든 스도쿠 맵을 돌면서 빈칸인 곳을 찾는 것이 비효율적이라고 생각했다. 그래서, 스도쿠 맵을 저장할 때, 비어있는 칸의 위치를 List에 저장해서 빈 칸들만 순회하도록 만들었다.

 

그리고, 빈 칸들에 들어갈 수 있는 모든 수를 넣어보면서, 적합한 수를 넣어주었다.

모든 수를 검사할 때는 빈칸의 가로와 세로에 어떤 수들이 나와있는지 boolean 배열을 통해 저장했다.

그 다음, 이 빈칸이 존재하는 하나의 박스(3 by 3의 칸)를 순회하며 나와있는 수들을 체크했다.

위의 두 검사를 마친 후, 아직 등장하지 않은 후보 숫자들을 List에 담아 리턴하는 메소드를 만들었다.

 

들어갈 수 있는 수의 리스트를 모두 넣어보면서 다음 빈칸으로 재귀함수를 돌도록 만들어주었다.

이 때, map 배열을 전역으로 공유하고 있기 때문에 답을 찾은 후 수정을 하지 않도록 found 변수를 두어 불필요한 순회 및 값 수정이 일어나지 않도록 설정했다.

 

메모리 효율이 좋지 않아서 최적화를 할 수 있는 방법을 생각해봐야 할 것 같다.

 

코드

 

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

public class Sudoku_2580 {
  static int[][] map;
  static List<Pair> emptyList;
  static boolean found;
  static final int LEN =3, MAX_LEN = 9, EMPTY =0;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    map = new int[MAX_LEN][MAX_LEN];
    emptyList = new ArrayList<>();
    for(int i = 0; i< MAX_LEN; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int j = 0; j< MAX_LEN; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
        if(map[i][j] == EMPTY) {
          emptyList.add(new Pair(j,i));
        }
      }
    }

    br.close();
    solution();
  }

  private static void solution() {
    sudoku(EMPTY);
    StringBuilder sb = new StringBuilder();
    final String NEW_LINE = "\n", SPACE = " ";

    for(int[] line : map) {
      for(int num : line) {
        sb.append(num).append(SPACE);
      }
      sb.append(NEW_LINE);
    }
    System.out.println(sb.toString());
  }

  private static void sudoku(int index) {
    if(found) {
      return;
    }
    if(index == emptyList.size()) {
      found = true;
      return;
    }
    Pair now = emptyList.get(index);
    List<Integer> numList = getNumList(now);
    for(int num : numList) {
      map[now.y][now.x] = num;
      sudoku(index+1);
      if(found) {
        return;
      }
      map[now.y][now.x] = EMPTY;
    }
  }

  private static List<Integer> getNumList(Pair now) {
    List<Integer> numList = new ArrayList<>();
    boolean[] exist = new boolean[MAX_LEN +1];
    
    for(int i = 0; i< MAX_LEN; i++) {
      exist[map[now.y][i]] = true; // 가로 탐색
      exist[map[i][now.x]] = true; // 세로 탐색
    }

    // 칸 탐색 // 0~2, 3~5, 6~9
    Pair scale = getScale(now);
    for(int y=3*scale.y; y<3*(scale.y+1); y++) {
      for(int x=3*scale.x; x<3*(scale.x+1); x++) {
        exist[map[y][x]] = true;
      }
    }

    for(int i=1; i<=MAX_LEN; i++) {
      if(!exist[i]) {
        numList.add(i);
      }
    }
    return numList;
  }

  private static Pair getScale(Pair now) {
    int xScale =LEN+1, yScale =LEN+1;
    for(int i=1; i<=LEN; i++) {
      if(now.x < LEN*i) {
        xScale = Math.min(xScale, i-1);
      }
      if(now.y < LEN*i) {
        yScale = Math.min(yScale, i-1);
      }
    }
    return new Pair(xScale, yScale);
  }

  private static class Pair {
    int x,y;
    public Pair(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
}