[java 백준] 골드 4/2580번 스도쿠

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

2580번: 스도쿠

 

import java.util.Scanner;
 
public class Main {
    public static int n;
    public static int[][] arr;
 
    public static StringBuilder sb = new StringBuilder();
 
    // 부모 노드로 돌아와야하는 기준 => 잘못된 값으로 진행한 경우 다시 0으로 초기화하여 부모노드로 돌아와야
 
    // 중복되는지 검사
    public static boolean check(int row, int col, int val) {
 
        // 가로에 동일한 숫자
 
        for (int i = 0; i < 9; i++) {
            if (arr[row][i] == val) {
                return false;
            }
        }
 
        // 세로에 동일한 숫자
        for (int i = 0; i < 9; i++) {
            if (arr[i][col] == val) {
                return false;
            }
        }
 
        // 3*3 블럭 안에 동일한 숫자
 
        int cols = ((col / 3) * 3);
        int rows = ((row / 3) * 3);
 
        for (int i = rows; i < rows + 3; i++) {
            for (int j = cols; j < cols + 3; j++) {
                if (arr[i][j] == val) {
                    return false;
                }
            }
 
        }
 
        return true;
 
    }
 
    public static void paint(int row, int col) {
        // 열이 다 채워졌을 경우 다음 행으로 ㄱㄱ
        if (col == 9) {
            paint(row + 1, 0);
            // 만약 잘못 입력했을 경우 부모노드로 되돌아가야함
            return;
 
        }
 
        if (row == 9) {
            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);
        }
 
        // 행이 다 채워졌을 경우 끝내기
 
        if (arr[row][col] == 0) {
            // 1부터 9까지의 애들 중 중복되지 않은 애를 넣어주기
            for (int i = 1; i <= 9; i++) {
                if (check(row, col, i)) {
                    arr[row][col] = i;
                    paint(row, col + 1);
 
                }
 
            }
            // 만약 채워지지 않는 경우/ 잘못된 값으로 진행했을 경우 다시 0으로 초기화하여 리턴
            // 예를들어 arr[row][col]에 5를 넣어줬는데 사실상 답이 5보다 더 작은 수이면
            // 이전으로 돌아갈 수 없기 때문에 차라리 0으로 바꿔주고 처음부터 다시 돌리는거
            arr[row][col] = 0;
            return;
            // 리턴이 있어야 다음열로 넘어가 탐색함. 중간에 리턴이 없으면 자리를 채웠는데 실패한 경우
            // 돌아오고 나서 다시 다음열을 탐색함.
        }
        // 만약 arr값이0이 아니면 열을 옮겨줘야함
        paint(row, col + 1);
 
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        arr = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
 
        // for문을 무지성으로 쓰지 않고 재귀 백트래킹을 하는게 중요
 
        paint(0, 0);
 
    }
 
}

 

 

https://st-lab.tistory.com/119

[백준] 2580번 : 스도쿠 - JAVA [자바]

 

https://easybrother0103.tistory.com/59

[알고리즘] 백준 2580 스도쿠 - JAVA

 

 

위의 두분의 블로그 글을 많이 참고해서 코드를 써봤다. 처음 쓴 코드는 아래 첨부해뒀는데 이 문제는 애초에 for문이 주가 아닌 문제였다.

빈칸을 채우는 노드의 기준은 

1. 현재노드를 기준으로 세로로 한줄에서 겹치는 노드가 없을때

2.현재 노드를 기준으로 가로로 한줄에서 겹치는 노드가 없을때

3. 현재 노드를 기준으로 현재 노드가 속한 3X3 사각형에서 겹치는 노드가 없을때

 

이 3가지 조건이 모두 만족해야 유망한 노드이다. 

 

세가지 조건을 모두 체크하는 함수인 check에서 true를 반환하면 arr값에 값이 들어간다. 

 

근데 백트래킹을 해야하는 상황은

 

1. 만일 사진 속 저 for문에서 원래 정답과 다른 값을 arr에 넣어주는 경우가 생길 수도 있다. check에서는 만족하지만 9줄을 끝까지 탐색했을 때는 정답이 아닌 숫자를 넣어준 경우는 다시 앞으로 가서 숫자를 바꿔줄 수 없기에 그냥 arr을 0으로 초기화 시켜줘야 한다.그리고 리턴을 해줘야 한다.   예시로 나온 값은 빈칸이 별로 없어서 왜 그렇게 생각해야하나 싶을 수 있지만 만약에 빈칸이 엄청 많을 경우 넣었다 뺐다를 해야하는데 이건 반복문을 가지고 해줄 수 가 없다. 반복문은 앞으로 돌아갈 수도 없기 때문에 걍 초기화를 시켜주는게 편하다.

 

 

2. 만약 col==9이면 다음 열로 넘어가야 하기 때문에 row+1을 해주고 return을 해줘야한다. return을 하는 이유는 만약 현재 row에서 잘못된 값을 입력한 경우 또 다시 부모 노드로 돌아가는 백트래킹을 해야하기 때문이다.

 

지금까지 return을 해주는게 부모 노드로 돌아가야 할때만이라 생각했는데 더 구체적으로는 잘못된 값이 입력/ 또는 값이 입력되지 않았기 때문에 부모노드로 돌아가기위해 return을 하는거였다.. ㄸㄹㄹ! 

 

흠,, 내가 쓰고도 잘 이해가 되지 않는다. 완전탐색을 다 풀고 다시 와서 또 풀어봐야할듯하다. 

 

++) 다시 정리

 

1.백트래킹 문제에서 return의 기준은 부모 노드로 다시 돌아가야할 때

2. 부모 노드로 돌아갈때 값들을 초기화 시켜주고 돌아가야함! (그래서 arr[row][co]=0으로 해주는거)

 

처음 썼던 코드 (틀린코드임)

package 백준;
 
import java.util.Scanner;
 
public class Main {
    public static int n;
    public static int[][] arr;
    public static int[] col;
    public static boolean[] visited;
    public static int[] dirX = { -1, 1, 0, 0 };
    public static int[] dirY = { 0, 0, -1, 1 };
    // 부모 노드로 돌아와야 하는 기준 => col 배열에 더이상 0이 없을 때
 
    public static void dfs(int std) {
        if (std == 10) {
            return;
        } else {
            for (int i = 1; i <= 9; i++) {
                if (arr[std][i] != 0) {
                    visited[arr[std][i]] = true;
 
                } else {
                    // 0인 애들 채워주기
                    for (int j = 1; j <= 9; j++) {
                        if (!visited[j]) {
                            for (int k = 0; k < 4; k++) {
                                if (j != arr[std + dirX[k]][j + dirY[k]]) {
                                    arr[std][i] = j;
                                    visited[j] = true;
 
                                }
                            }
 
                        }
                    }
 
                }
            }
 
            for (int i = 1; i <= 9; i++) {
                visited[i] = false;
            }
            dfs(std + 1);
        }
 
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        arr = new int[12][12];
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
 
        visited = new boolean[10];
        dfs(1);
 
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
 
    }
 
}