자바(백준) 2580 스도쿠

오답 노트 & 새로 알게 된 점

처음에 isConditionTrue를 작성할 때, 행, 열에서 검사하는 것은 쉽게 생각했지만 3*3일 때는 검사를 하기 위해선 총 9개의 범위를 나눠야 하는 생각이 들었다.  하지만 이 9개 범위를 다 나누는 것은 효율적이지 않고, 어떠한 방법이 있을 것이라 생각했다. 그래서 구글링을 하여 힌트를 얻었다. 

- 이러한 문제를 풀 때, 규칙성을 찾고 구현하는 실력을 쌓아야겠다.

 

처음에 backTracking을 돌릴 때, sdk ArrayList에 저장되어 있는 것을 어떻게 꺼내올지가 고민이었다. 이게 무슨 말이냐면, 내가 스도쿠를 입력할 때 숫자가 0 이면 따로 ArrayList에 저장을 했는데, 이 ArrayList 안에 있는 좌표를 어떻게 꺼내올까라는 것이 고민이었다. 반복문을 쓰기에는 스도쿠 숫자 범위가 1~9인데, ArrayList의 size가 꼭 9가 아니라는 점이었다. 그래서 backTracking의 인자로 index를 집어넣어 새로운 그 해당 index의 x, y 좌표를 얻었다.

 

사용 개념

재귀 함수

 

코드

package BackTracking;
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int arr[][] = new int[9][9];
    static ArrayList<SdkPoint> sdk = new ArrayList<>();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        for(int i = 0; i < 9; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 9; j++){
                int num = Integer.parseInt(st.nextToken());
                arr[i][j] = num;
                if(num == 0) sdk.add(new SdkPoint(i, j));
            }
        }
 
        backTracking(0,0);
 
    }
    static void backTracking(int index, int count){
        if(count == sdk.size()){
            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);
        }
 
        int x = sdk.get(index).x;
        int y = sdk.get(index).y;
 
        for(int i = 1; i <= 9; i++){
            if(isConditionTrue(x, y, i)){
                arr[x][y] = i;
                backTracking(index + 1, count + 1);
                arr[x][y] = 0;
            }
        }
    }
 
    static boolean isConditionTrue(int row, int col, int value){
 
        for(int i = 0; i < 9; i++){
            if(arr[row][i] == value || arr[i][col] == value)
                return false;
        }
 
        row = (row / 3) * 3;
        col = (col / 3) * 3;
 
        for(int i = row; i < row + 3; i++){
            for(int j = col; j < col + 3; j++){
                if(arr[i][j] == value)
                    return false;
            }
        }
        return true;
    }
 
}
 
class SdkPoint{
    int x, y;
    SdkPoint(int x, int y){
        this.x = x;
        this.y = y;
    }
}

 

---

오답 노트 & 새로 알게 된 점 (2021.10.14)

백트래킹 공부를 하면서 유명한 스도쿠 문제를 한번 더 풀어보았다.

 

어느 한 부분 때문에 1~2시간 가량 막혔다.

 

코드를 보면 pro메서드에 있는 출력과, main메서드에 있는 출력(주석 처리)가 있다.

 

처음에 나는 pro메서드에서 cnt가 zeroArea의 size와 개수가 같으면 flag을 true로 하여,

처음 스도쿠를 만들게 되면 나머지는 탐색을 하지 않는 방법을 사용했다.

 

그래서 pro메서드에서 탐색을 모두 완료한 뒤, main 메서드에서 출력을 하면 답이 나올 것이라 생각했지만

출력해보면 입력 그대로 나오게 된다.

 

왜 이게 안되지? 문법적으로 오류는 없는데 왜 계속 탐색을 할까 일일이 디버깅을 다해보았다.

 

pro메서드에서 출력을 하지 않게되면, pro가 끝날 때까지

코드에서 ' 이 부분 ' 이라는 곳이 계속해서 실행이 된다.

그래서 A의 배열 값들을 모두 0으로 하고 계속 flag를 만나 return 하게 된다.

 

결국 탐색만 다하고 마지막에 원상복귀를 시켜놓는 것이다.

그래서 pro메서드가 끝나고 main에서 출력을 하게 되면 입력이 그대로 출력된다...

 

이 부분 때문에 엄청 고민을 했었다.. 이건 아직 백트래킹이 익숙하지 않아서 생긴 것 같다.

다음에는 이러한 잘못을 절대 저지르지 않을 것이다.

 

---

2021.11.29

한달만에 풀어본 스도쿠 문제이다.

한달만에 다시 풀어도 틀리는 것을 보니, 한 번 맞았던 문제여도 다시 풀어보는 것이 중요한 것 같다.

 

처음 시도했을 때

이런 식으로 구현했다.

A배열에 숫자를 넣은 뒤, check 메서드에서 이 숫자가 들어가도 되는지 안되는지 판단했다.

그러나 이렇게 코드를 작성하면 답 자체가 틀렸다고 나온다.

 

그래서 위와 같이 현재 넣을 숫자를 먼저 check메서드에서 판단한 다음에

넣을 수 있다면, 그 때 A 배열에 숫자를 넣어주었다.

 

---

코드

package BackTracking;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
 
    static class Point{
        int x, y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int A[][] = new int[9][9];
    static ArrayList<Point> zeroArea = new ArrayList<>();
    static int zero;
    static boolean flag = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                A[i][j] = atoi(st.nextToken());
                if(A[i][j] == 0){
                    zeroArea.add(new Point(i, j));
                }
            }
        }
 
        pro(0);
 
        /*for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(A[i][j] + " ");
            }
            System.out.println();
        }*/
    }
 
    static void pro(int cnt) {
        if(flag) return;
 
        if (cnt == zeroArea.size()) {
            flag = true;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(A[i][j] + " ");
                }
                System.out.println();
            }
            return;
        }
 
 
 
        for (int i = 1; i <= 9; i++) {
            if (possible(i, cnt) == false) {
                A[zeroArea.get(cnt).x][zeroArea.get(cnt).y] = i;
                pro(cnt + 1);
                A[zeroArea.get(cnt).x][zeroArea.get(cnt).y] = 0; // <-- 이 부분
            }
        }
    }
 
    static boolean possible(int value, int zero) {
        int row = zeroArea.get(zero).x;
        int col = zeroArea.get(zero).y;
 
       //행 비교
        for (int i = 0; i < 9; i++) {
            if(A[i][col] == value || A[row][i] == value) return true;
        }
 
        row = (row / 3) * 3;
        col = (col / 3) * 3;
 
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                if(value == A[i][j]) return true;
            }
        }
 
        return false;
    }
}