[BOJ] 2239 스도쿠 - JAVA

1. 문제

2239번: 스도쿠

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

---

2. 풀이

입력 및 출력

판을 입력받으면서 0 위치를 list에 모두 저장한다. 이 문제는 같은 답이 여러 개 있다면 숫자가 작은 순으로 0이 채워져야하기 때문이다. 이렇게 입력받으면서 list를 채우고, 그 순서대로 답을 넣으면 신경 쓰지 않아도 알아서 숫자가 작은 순으로 채워진다.

리스트는 int[] 타입으로, 가로 세로 위치를 모두 넣는다.

입력받은 뒤 go탐색함수를 실행한다.

실행 후에는 정답으로 바뀐 sudoku 배열을 StringBuilder에 모아서 한 번에 출력한다.

static int[][] sudoku = new int[9][9];
static ArrayList<int[]> list = new ArrayList<>();

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   for (int i = 0; i < 9; i++) {
      String line = in.readLine();
      for (int j = 0; j < 9; j++) {
         sudoku[i][j] = line.charAt(j)-'0';
         if(sudoku[i][j]==0) list.add(new int[]{i,j});
      }
   }

   go(0);

   StringBuilder sb = new StringBuilder();
   for(int i=0;i<9;i++){
      for(int j=0;j<9;j++){
         sb.append(sudoku[i][j]);
      }
      sb.append('\n');
   }

   System.out.print(sb);
}

 

탐색

1. list의 사이즈만큼 재귀호출할 것이다. 한 칸을 채울 때마다 cnt+1을 해서 cnt==list.size()면 답이 완성된 것이므로 끝낸다. 다른 경우의 수를 더 이상 탐색하지 않기 위해서 true를 반환한다. 

2. 현재 0 위치에 1부터 9까지 모두 넣어본다.

3. 그 위치가 가능한지, 가능하다면 그 다음 재귀의 답이 true로 반환되는지(답 완성된 것) 체크한다. 둘 다 가능하다면 함수를 true반환하며 끝낸다.

4. i가 가능해도 그 다음 재귀의 답이 false이거나, 애초에 i가 불가능하면 다음 i를 넣어본다.

5. i를 9까지 전부 시도했는데도 답이 나오지 않았다면 그 자리를 0으로 바꾸고 false를 반환한다.  

private static boolean go(int cnt){
   if(cnt==list.size()) return true;

   int y = list.get(cnt)[0];
   int x = list.get(cnt)[1];
   for(int i=1;i<10;i++){
      sudoku[y][x] = i;
      if(isValid(y,x) && go(cnt+1)) return true;
   }

   sudoku[y][x] = 0;
   return false;
}

 

범위체크(1)

1. 가로 세로 중 하나라도 같은 값이 있다면 false를 반환한다.

2. i,j가 속한 3*3 칸을 탐색해서 하나라도 같은 값이 있다면 false를 반환한다.

3. 3*3칸을 탐색하려면 그 칸의 첫 번째 위치를 알아야 한다. i를 3으로 나눈 몫에 3을 다시 곱하면 첫번째 위치가 된다.

4. 위에서 false 반환되지 않았다면 true를 반환하고 끝낸다.

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

   for(int ni=(i/3)*3,k=0;k<3;k++,ni++){
      for(int nj=(j/3)*3,l=0;l<3;l++,nj++){
         if(ni!=i && nj!=j && sudoku[ni][nj]==sudoku[i][j]) return false;
      }
   }

   return true;
}

 

범위체크(2) - 다른 방법

바로 위의 방법도 가능하고 이 방법도 가능하다. go 함수에서 받은 x,y 위치에 가능한 숫자를 저장한 boolean 배열을 반환한다.

이러면 여러번 함수에 접근할 필요도 없고 한 번 반복하면서 여러 숫자를 탐색할 수 있기 때문에 시간이 많이 단축된다.

하지만 자리마다 10칸 배열을 사용하기 때문에 메모리가 더 많이 든다.

private static boolean[] isValid(int i, int j){
	boolean[] res = new boolean[10];
	for(int k=0;k<9;k++){
		res[sudoku[k][j]] = true;
		res[sudoku[i][k]] = true;
	}

	for(int ni=(i/3)*3,k=0;k<3;k++,ni++){
		for(int nj=(j/3)*3,l=0;l<3;l++,nj++){
			res[sudoku[ni][nj]] = true;
		}
	}
	return res;
}

---

3. 결과

아래에 있는 경우(메모리 적고 시간 많이 든 경우)가 범위체크(1)을 사용한 코드다.

위의 코드가 범위체크(2)를 사용한 코드다. 시간은 절반, 메모리는 11배 정도 더 늘었다. 이 정도 차이라면 시간을 포기하고 메모리를 챙기는 방향이 맞아보인다.

 

풀고 보니 [BOJ] 2580 스도쿠 와 풀이방식이 거의 똑같다.