[JAVA] 백준 2580번: 스도쿠

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

 

문제 풀이

 

1. 0이 위치한 행,열 위치정보를 어레이에 넣는다. 

- 빈칸이 문제에서는 0으로 주어지고 있다.

- 우리가 채워야 할 칸은 0이기 때문에 0이 있는 좌표만 가져온 다음 해당 좌표에서 행, 열, 3x3 에 위치한 수와 겹치지 않는 수를 넣으면 된다.

코드는 아래와 같다. ( 값을 받으면서 동시에 값이 0이 경우에는 ary에 집어 넣고 있다.)

Scanner sc = new Scanner(System.in);
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    int temp = sc.nextInt();
    info[i][j] = temp;
    if (temp == 0) {
      ary.add(new int[] {i,j});
    }                
  }
}

 

2. 같은 행에 있는 원소 중에 겹치는 수가 있는지를 검사한다.

static boolean backtrackingRow(int h, int w, int target) {
    for (int i = 0; i < n; i++) {
        if (info[h][i] == target) {
            return false;
        }
    }
    return true;
}

3. 같은 열에 있는 원소 중에 겹치는 수가 있는지를 검사한다.

- 사실 행과 열을 확인하는 작업은 하나의 for문으로 백트래킹이 가능하지만 메소드를 두개로 나누는 것이 의도를 파악하기 더 좋아보여서 아래와 같이 코드를 구현하였다.

static boolean backtrackingCol(int h, int w, int target) {
    for (int i = 0; i < n; i++) {
        if (info[i][w] == target) {
            return false;
        }
    }
    return true;
}

4. 해당 위치에 속한 3×3 칸에 중복되는 수가 있는지를 검사한다.

- 메소드 이름을 뭐라고 지었으면 좀 더 직관적이었을까...

static boolean backTrackingSquare(int h, int w, int target) {
    for (int i = h; i <= h + 2; i++) {
        for (int j = w; j <= w + 2; j++) {
            if (info[i][j] == target) {
                return false;
            }
        }
    }
    return true;
}

5. 모든 빈칸을 채웠다면 결과를 출력하고, 종료하자.

- count의 수가 ary에 들어있는 원소의 수와 같다는 것은 모든 0을 다 채웠다는 의미다.

- 결과값을 출력해주고 종료하자

 

 

if (count == ary.size()) {
    // 결과 출력            
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.print(info[i][j]+" ");
        }
        System.out.println();
    }
    System.exit(0);            
}

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
 
    static int n = 9;    
    static int[][] info = new int[n][n];    
    static ArrayList<int[]> ary = new ArrayList<>();
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = sc.nextInt();
                info[i][j] = temp;
                if (temp == 0) {
                    ary.add(new int[] {i,j});
                }                
            }
        }
        sudoku(0);                
    }
 
    static void sudoku(int count) {        
        if (count == ary.size()) {
            // 결과 출력            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(info[i][j]+" ");
                }
                System.out.println();
            }
            System.exit(0);            
        }
        
        int[] location = ary.get(count);
        int h = location[0];
        int w = location[1];                
        
        for (int i = 1; i <= n; i++) {
            int squareH = (h / 3) * 3;
            int squareW = (w / 3) * 3;            
            if (backTrackingSquare(squareH, squareW, i) && backtrackingCol(h, w, i) && backtrackingRow(h, w, i)) {                
                info[h][w] = i;
                sudoku(count+1);                
            } 
        }       
        info[h][w]=0;
    }
 
    static boolean backtrackingRow(int h, int w, int target) {
        for (int i = 0; i < n; i++) {
            if (info[h][i] == target) {
                return false;
            }
        }
        return true;
    }
 
    static boolean backtrackingCol(int h, int w, int target) {
        for (int i = 0; i < n; i++) {
            if (info[i][w] == target) {
                return false;
            }
        }
        return true;
    }
 
    static boolean backTrackingSquare(int h, int w, int target) {
        for (int i = h; i <= h + 2; i++) {
            for (int j = w; j <= w + 2; j++) {
                if (info[i][j] == target) {
                    return false;
                }
            }
        }
        return true;
    }
}