스도쿠(2580)

조금 더 복잡한 백트래킹 문제 2

문제

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

img

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

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

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

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

img

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

img

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

img

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

입력

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

출력

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

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

제한

• baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.

  • C++14: 80ms

  • Java: 292ms

  • PyPy3: 1172ms

예제 입력

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

예제 출력

1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

에러가 뜨고 있는데 왜지..? 설마 벡터하나썼다고??

답뒤져보니까 ArrayList를 많이쓰던데

-> 이문제는 아니고

아니면 반례가 있는건가

-> 다 0을 넣고 돌리면 무한으로 계속 나옴 이거 해결해봐야할듯

이게 print하는 부분에서 마지막에 그냥 return해줬는데 이렇게하니까 무한으로 돌아가는 그런 현상이 일어난거같다...

만약에 끝내야하는 상황이 온다면 그때는 return을 사용하지 말고 System.exit(0) 을 사용해서 그냥 프로그램을 종료시키자 실제로 이렇게 바꾸니까 맞음...

풀이

import java.io.*;
import java.util.*;

public class Main{
    static int arr[][] = new int[9][9];
    //빈 자리의 포인트를 벡터로 저장
    static ArrayList<Point> al = new ArrayList<>();
//    static Vector<Point> v = new Vector<>();
    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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                //여기서 입력받은 숫자가 0이면 벡터에 저장해둔다.
                if(arr[i][j] == 0)
                    al.add(new Point(i, j));
            }
        }
        dfs(0);
    }

    public static void dfs(int depth){
        if(depth==al.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 = al.get(depth).x;
        int y = al.get(depth).y;

        for (int i = 1; i <= 9; i++) {
            if(check(x,y,i)){
                arr[x][y] = i;
                dfs(depth+1);
                arr[x][y] = 0;
            }
        }

    }


    public static boolean check(int x, int y, int num){
        //0일때 진행해야하기 때문에,
        if(arr[x][y] == 0) {
            for (int i = 0; i < 9; i++) {
                //가로, 세로에  num이 존재하는지 확인,
                if(arr[i][y] == num || arr[x][i] == num)
                    return false;
            }
            //현재 좌표가 3x3 기준으로 어디 박스에 있는지를 체크하고 그 박스의 시작점으로 위치하시키기 위한 변수,
            int sx = x/3*3;
            int sy = y/3*3;

            //박스를 돌면서 3개씩 위아래로 num이 존재하는지 확인,
            for (int i = sx; i < sx+3; i++) {
                for (int j = sy; j < sy+3; j++) {
                    if(arr[i][j] == num)
                        return false;
                }
            }
        }
        return true;

    }

    public static class Point{
        private int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}

백준

2번째 시도

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;
    static boolean[][] visited;
    static ArrayList<int[]> list;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        arr = new int[9][9];
        visited = new boolean[9][9];
        list = new ArrayList<>();

        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 9; j++) {
                int recv = Integer.parseInt(st.nextToken());
                arr[i][j] = recv;
                //위는 값을 입력받아서 배열에 집어넣어주는 과정인데
                //입력받을 때 0(빈칸)을 체크해둬야 0을 기준으로 값을 넣을 수 있는지 검증할 수 있다.
                if (recv == 0)
                    list.add(new int[]{i, j});
            }
        }
        dfs(0);

    }

    //dfs를 구현한 함수
    public static void dfs(int cnt) {
        //여기서도 살짝 헤멨는데 깊이를 의미하는 cnt를 돌리게되는데 이걸 0의 갯수를 기록해둔 arraylist를 기준으로 잡으면 됬다.
        if (cnt == list.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);
        }

        //검사하는 함수를 만들긴했지만 문제가 있었던건 0을 체크해서 기록해둬야하는데 어떻게 기록해야하나였다.
        //여기부분은 뭔가 알것 같으면서도 헷갈려서 찾아봤는데 기존에는 vector를 사용해서 구현했었고, arraylist가 적절했다.
        //그래서 x,y값을 순서대로 가지고 있는 1차원 배열을 생성해서 순서대로 넣고 그 배열들을 가진 arraylist를 만듬
        
        //체크하는 방식은 1~9를 순서대로 넣으면서 값이 들어갈 수 있는지 확인
        for (int i = 1; i <= 9; i++) {
            //기존에 만든 검사여부를 확인해서 모두 만족시 dfs진행
            if (rowCheck(list.get(cnt)[0], list.get(cnt)[1], i) && squareCheck(list.get(cnt)[0], list.get(cnt)[1], i)) {
                //성공했다는 의미는 값이 들어갈 수 있다는 의미이기 떄문에 값 넣어주고
                arr[list.get(cnt)[0]][list.get(cnt)[1]] = i;
                //다음 0자리로 넘어가서 진행
                dfs(cnt + 1);
                //만약 진행과정에서 문제가 생겨서 함수를 튀어나올 시, 이전에 진행했던 값을 취소해줘야 위에서 다음 것으로 진행한 것을 다시 되돌릴 수 있다.
                arr[list.get(cnt)[0]][list.get(cnt)[1]] = 0;
            }
        }
    }

    //입력받은 스도쿠판의 좌표에 숫자가 들어갈 수 있는지 체크하는 함수들 -> 좌표와 어떤 값이 들어갈 수 있는지 확인해서 가능/불가능으로 체크
    
    //가로와 세로줄에 숫자가 들어갈 수 있는지 확인하는 함수
    public static boolean rowCheck(int x, int y, int num) {
        for (int i = 0; i < 9; i++) {
            if (arr[i][y] == num || arr[x][i] == num)
                return false;
        }
        return true;
    }

    //3x3박스에 숫자가 들어갈 수 있는지 확인하는 함수
    public static boolean squareCheck(int x, int y, int num){
        //어떠한 좌표가 들어왔을 때 어떤 박스에 해당하는지 확인하기 위해서
        //모든 좌표를 그리고 숫자를 들여다보니까 이렇게 공식을 적으면 가능하다는 것을 알게됨
        int startX = x / 3 * 3;
        int startY = y / 3 * 3;

        for (int i = startX; i < startX + 3; i++) {
            for (int j = startY; j < startY + 3; j++) {
                if (arr[i][j] == num)
                    return false;
            }
        }
        return true;
    }

}