[BOJ] 2580. 스도쿠(백트래킹).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

백트래킹 기본 문제이다.

기본적인 로직은 빈칸에 1~9까지의 숫자를 넣어보고

가로줄, 세로줄, 3x3구역을 확인하고

빈칸에 해당 숫자를 넣을 수 있다면 다음 칸에도 동일하게 시도해보면 된다.

한 가지 고민(?)해야할 부분은

빈칸이 해당하는 3x3구역의 시작점을 찾은 방법인데,

몇 가지의 예시를 생각해보면 금방 찾을 수 있다.

4, 1 의 3x3구역 시작점 : 3, 0 

4/3*3, 1/3*3

7, 1 의 3x3구역 시작점 : 6, 0

6/3*3, 0/3*3

5, 5 의 3x3구역 시작점 : 3, 3

3/3*3, 3/3*3

3x3구역 시작점을 구하는 식은

아래와 같이 세울 수 있다.

sr = r / 3 * 3, sc = c / 3 * 3;

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class BOJ2580 {       static int N = 9, M, map[][];     static ArrayList<Point> blanks;          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  map = new int[N][N];         blanks = new ArrayList<>();         for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());             for (int j = 0; j < N; j++) {                 map[i][j] = Integer.parseInt(st.nextToken());                 if(map[i][j] == 0) blanks.add(new Point(i, j));             }         }                  M = blanks.size();         process(0);         for (int i = 0; i < N; i++) {             for (int j = 0; j < N; j++) {                 System.out.print(map[i][j] + " ");             }             System.out.println();         }     }       private static boolean process(int cnt) {           // 모든  칸을 다 채웠을 경우         if(cnt == M) return true;                  // 1~9까지 빈 칸에 넣어보자.         Point now = blanks.get(cnt);         for (int i = 1; i <= 9; i++) {             map[now.r][now.c] = i;                          // 빈 칸에 현재 숫자를 넣을 수 있다면 다음 칸에 넣어보자.             if(check(now.r, now.c, i)) {                 if(process(cnt + 1)) return true;             }         }                  // 원상복구         map[now.r][now.c] = 0;                  return false;     }       private static boolean check(int r, int c, int num) {                  // 가로줄 확인         for (int i = 0; i < N; i++) {             if(i == c) continue;             // 동일한 숫자가 있을 경우             if(map[r][i] == num) return false;         }                  // 세로줄 확인         for (int i = 0; i < N; i++) {             if(i == r) continue;             // 동일한 숫자가 있을 경우             if(map[i][c] == num) return false;         }                  // 3x3 구역 확인         int sr = r / 3 * 3, sc = c / 3 * 3;         for (int i = sr; i < sr + 3; i++) {             for (int j = sc; j < sc + 3; j++) {                 if(i == r && j == c) continue;                 // 동일한 숫자가 있을 경우                 if(map[i][j] == num) return false;             }         }                  return true;     }       static class Point {         int r, c;           public Point(int r, int c) {             this.r = r;             this.c = c;         }       } }   Colored by Color Scripter

cs

#. Code_v2

최적화된 방법을 참고하여 다시 해결한 코드이다.

이렇게 또 깨달음을 얻고 간다ㅏ..

첫 번째 방법에서는 모든 경우에서 가로줄, 세로줄, 3x3구역을 체크해주었다.

하지만, 두 번째 방법에서는 

가로줄, 세로줄, 3x3구역에 어떤 숫자가 들어있는지 상태를 관리해주는 boolean 배열로

최적화를 해줄 수 있었다.

* 자세한 설명은 코드 하단

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class BOJ2580_v2 {
 
    static int N = 9, M, map[][];
    static boolean[][] row, col, squ; 
    static ArrayList<Point> blanks;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        map = new int[N][N];
        row = new boolean[N][N + 1];
        col = new boolean[N][N + 1];
        squ = new boolean[N][N + 1];
        blanks = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                
                if(map[i][j] == 0) blanks.add(new Point(i, j));
                else {
                    // i 행에서 map[i][j] 숫자가 사용
                    row[i][map[i][j]] = true;
                    // j 열에서 map[i][j] 숫자가 사용
                    col[j][map[i][j]] = true;
                    // 해당 좌표가 해당하는 3x3구역에서 map[i][j] 숫자가 사용
                    squ[(i/3*3) + (j/3)][map[i][j]] = true;
                }
            }
        }
        
        M = blanks.size();
        process(0);
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(map[i][j] + " ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb);
    }
 
    private static boolean process(int cnt) {
 
        // 모든 빈칸을 다 채웠을 경우
        if(cnt == M) return true;
        
        // 1~9까지 빈칸에 넣어보자.
        Point now = blanks.get(cnt);
        for (int i = 1; i <= 9; i++) {
            // 해당 숫자가 가로줄 or 세로줄 or 3x3구역에 포함되었다면 pass 
            if(row[now.r][i] || col[now.c][i] || squ[(now.r/3*3) + (now.c/3)][i]) continue;
            
            // 빈칸에 현재 숫자를 넣을 수 있다면
            row[now.r][i] = true;
            col[now.c][i] = true;
            squ[(now.r/3*3) + (now.c/3)][i] = true;
            map[now.r][now.c] = i;
            
            // 다음 빈칸으로
            if(process(cnt + 1)) return true;
            
            // 원상복구
            row[now.r][i] = false;
            col[now.c][i] = false;
            squ[(now.r/3*3) + (now.c/3)][i] = false;
            map[now.r][now.c] = 0;
        }
        
        return false;
    }
 
    static class Point {
        int r, c;
 
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
 
    }
}
 

line 31) 해당 행에 어떤 숫자가 사용되었는지 상태를 저장해준다.

line 33) 해당 열에 어떤 숫자가 사용되었는지 상태를 저장해준다.

line 35) 해당 구역에 어떤 숫자가 사용되었는지 상태를 저장해준다.

구역은 0~8구역까지 있다. 

예로 (4, 1)에 사용된 숫자는 3구역에 해당하고,

(6, 6)에 사용된 숫자는 8구역에 해당한다.

line 61~79) 1~9까지 빈칸에 넣어본다.

line 63) 상태를 저장해둔 boolean 배열을 활용해서

해당 숫자가 가로줄, 세로줄 혹은 3x3구역에 사용되었는지 확인해주자.

line 66~69) 해당 숫자가 사용되지 않았다면 

boolean 배열에 사용했다는 상태를 저장해주고, 빈칸에 채워주자.

line 72) 다음 칸도 동일하게

line 75~78) 해당 숫자를 사용해보았다면 다른 숫자도 사용해보기 위해

변경된 상태를 원상복구시켜주자.