[백준]2580: 스도쿠 - JAVA

[백준]2580: 스도쿠

www.acmicpc.net/problem/2580

2580번: 스도쿠

풀이

백트레킹 문제이다.

ArrayList를 사용해 0이 입력된 좌표의 위치를 저장하고, list에 담긴 좌표를 하나씩 꺼내 해당 위치에 들어갈 수 있는 숫자를 찾아주었다. 없으면 다음 좌표를 탐색하도록 구현했다.

 

list의 저장된 좌표를 모두 탐색하였다면 더 이상 탐색하지 않아도 되므로 출력을 해주고 아예 프로그램을 종료해 버린다. 여기서 종료해 주지 않고 return을 해주면 틀렸다고 된다. 

 

여기서 중요한 점은 0이 있는 좌표에 i값이 들어갈 수 있는지 확인하는 부분이다. i값은 1부터 9까지중 하나이다.

가로줄, 세로줄을 검사하는 방법은 반복문을 돌면서 i와 같은 값이 있는지 검사해주면 되므로 어렵지 않다ㅡ

 

다음으로 0이 있는 좌표가 해당하는 9칸 범위 내에 i와 같은 값이 있는지 검사하는 부분을 생각해 주어야 한다. 

원래 수도쿠를 배열로 표현하였으므로 각 좌표의 값은 아래와 같고 같은 색의 부분끼리 같은 범위내여야 한다.

0,0	0,1	0,2	0,3	0,4	0,5	0,6	0,7	0,8
1,0	1,1	1,2	1,3	1,4	1,5,	1,6	1,7	1,8
2,0	2,1	2,2,	2,3	2,4	2,5	2,6	2,7	2,8
3,0	3,1	3,2	3,3	3,4	3,5,	3,6	3,7	3,8
4,0	4,1	4,2	4,3	4,4	4,5	4,6	4,7	4,8
5,0	5,1	5,2	5,3	5,4	5,5	5,6	5,7	5,8
6,0	6,1	6,2	6,3	6,4	6,5	6,6	6,7	6,8
7,0	7,1	7,2	7,3	7,4	7,5	7,6	7,7	7,8
8,0	8,1	8,2	8,3	8,4	8,5	8,6	8,7	8,8

 

같은 범위에서 가장 왼쪽 위의 좌표값을 기준 값으로 정한다음 해당 좌표를 nx, ny라고 했을때 nx + 3, ny + 3 범위 내의 값이 i와 같은지 확인하면 된다. 이때 각 위치에서 계산되어야 하는 기준 값은 다음과 같다.

0,0	0,0	0,0	0,3	0,3	0,3	0,6	0,6	0,6
0,0	0,0	0,0	0,3	0,3	0,3	0,6	0,6	0,6
0,0	0,0	0,0	0,3	0,3	0,3	0,6	0,6	0,6
3,0	3,0	3,0	3,3	3,3	3,3	3,6	3,6	3,6
3,0	3,0	3,0	3,3	3,3	3,3	3,6	3,6	3,6
3,0	3,0	3,0	3,3	3,3	3,3	3,6	3,6	3,6
6,0	6,0	6,0	6,3	6,3	6,3	6,6	6,6	6,6
6,0	6,0	6,0	6,3	6,3	6,3	6,6	6,6	6,6
6,0	6,0	6,0	6,3	6,3	6,3	6,6	6,6	6,6

 

그럼 이제 각 좌표에서 위에 값 처럼 계산이 되도록 식을 세우기만 하면 된다.

예를들어서 0의 좌표가 5,6이라고 했을때 nx, ny를 구해보자. 5,6은 보라색으로 색칠한 칸에 속하므로 nx, ny가 3, 6이 나와야 한다.

 

우선 범위를 3개로 나눠야 하므로 좌표를 3으로 나눠준다. 그 다음 값의 단위가 3씩 커지므로 *3을 해주면 된다.

즉 nx  = x / 3 * 3, ny = y / 3 * 3이된다.

그리고 nx ~ nx + 3, ny ~ ny + 3까지의 범위 안에 i가 있는지 확인하면 된다.

 

코드

import java.util.*;
 
public class Main {    
    
    static ArrayList<Node> list; //0이 있는 좌표를 저장한다.
    static int[][] board;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        list = new ArrayList<>();
        board = new int[9][9];
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                board[i][j] = scan.nextInt();
                if(board[i][j] == 0) list.add(new Node(i, j));
            }
        }
        
        backtracking(0);
    }
    
    public static void backtracking(int idx) {
        if(idx == list.size()) {
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) {
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
            System.exit(0);
        }
        
        Node node = list.get(idx);
        for(int i = 1; i <= 9; i++) {
            if(check(node.x, node.y, i)) {
                board[node.x][node.y] = i;
                backtracking(idx + 1);
                board[node.x][node.y] = 0;
            }
        }
    }
    
    public static boolean check (int x, int y, int value) {
        //가로, 세로 검사
        for(int i = 0; i < 9; i++) {
            if(board[x][i] == value) return false;//가로줄에 value와 같은 값이 있다면 false
            if(board[i][y] == value) return false;//세로줄에 value와 같은 값이 있다면 false
        }
        
        //9칸 검사
        int nx = x / 3 * 3; //9칸의 시작x 좌표를 구함
        int ny = y / 3 * 3; //9칸의 시작y좌표를 구함
        for(int i = nx; i < nx + 3; i++) {
            for(int j = ny; j < ny + 3; j++) {
                if(board[i][j] == value) return false;
            }
        }
        
        return true;
    }
    
    public static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}