문제 링크 - https://www.acmicpc.net/problem/2239
🌱 문제
🌱 풀이
- 0인 칸에 스도쿠의 규칙을 만족하는 선에서 넣을 수 있는 숫자(1~9)를 전부 넣어보는 완전탐색(?)처럼 풀었다.
arr[][]
을 돌면서 0인 좌표를 리스트에 담아놓는다.
- 재귀함수로 리스트의 인덱스를 인자로 보내고, 리스트에 있는 좌표에 수를 전부 할당하면 배열을 main함수를 종료한다. (답이 여러개라면 사전식으로 앞서는 것을 출력해야 하기 때문에)
- 0인 좌표에 수를 할당하는 방식은 아래와 같은 방법을 이용해 찾는다.
0. boolean 배열을 선언하여, 이미 사용된 수를 true로 체크한다.
1. 해당 좌표와 같은 열에서 사용된 수를 체크한다.
2. 해당 좌표와 같은 행에서 사용된 수를 체크한다.
3. 해당 좌표가 해당하는 3x3(스도쿠 규칙) 배열에서 사용된 수를 체크한다.
- check배열을 돌면서 사용하지 않은 수를 현재 좌표에 할당하고 다음 재귀함수로 넘어간다.
주의할점
boolean check[] = new boolean[10];
- 수의 사용 여부를 확인하는 check배열을 지역이 아닌 전역으로 선언해서 엄청 헤맸다.
- 함수를 돌다가, 답이 될수 없는 경우임을 확인하고 이전 인덱스의 상태로 돌아갈 경우, 그때까지의 check 상태를 알고 있어야 하기 때문에 지역변수로 선언해서 관리해줘야 한다.!!!
🌱 코드
package boj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class boj_2239 {
static class Point {
int r, c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
@Override
public String toString() {
return "Point [r=" + r + ", c=" + c + "]";
}
}
static int arr[][];
static int listSize;
static boolean check[];
static ArrayList<Point> list;
static ArrayList<Integer> nums;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
arr = new int[9][9];
list = new ArrayList<Point>();
nums = new ArrayList<Integer>();
String s;
for (int i = 0; i < 9; i++) {
s = br.readLine();
for (int j = 0; j < 9; j++) {
arr[i][j] = s.charAt(j) - '0';
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (arr[i][j] == 0) {
list.add(new Point(i, j));
}
}
}
listSize = list.size();
func(0);
}
public static void func(int index) {
if (index == listSize) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
System.exit(0);
}
Point cur = list.get(index);
boolean check[] = new boolean[10];
for (int i = 0; i < 9; i++) {
int num=arr[i][cur.c];
if(num!=0 && check[num]==false)
check[num]=true;
}
for (int i = 0; i < 9; i++) {
int num=arr[cur.r][i];
if(num!=0 && check[num]==false)
check[num]=true;
}
int startR = cur.r/3 * 3;
int startC = cur.c/3 * 3;
for (int i = startR; i < startR + 3; i++) {
for (int j = startC; j < startC + 3; j++) {
int num=arr[i][j];
if(num!=0 && check[num]==false)
check[num]=true;
}
}
for (int i = 1; i <= 9; i++) {
if (check[i] == false) {
arr[cur.r][cur.c] = i;
func(index + 1);
arr[cur.r][cur.c] = 0;
}
}
}
}