[백준] 2580번 : 스도쿠[Java]

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

2580번: 스도쿠

 

풀이

DFS를 사용하여 스도쿠의 빈 칸에 모든 수를 집어넣고 각 경우마다 스도쿠가 될 수 있는지 체크한다.

 

로직

1. 스도쿠의 빈 칸 좌표를 ArrayList<int[]> points에 넣는다.

2. sudoku(idx:0)을 호출한다. 이 때 idx는 points의 인덱스다.

3. points에서 좌표를 꺼내고, for문으로 1~9까지 해당 좌표에 들어갈 수 있는지 check() 함수를 통해 체크한다.

• 들어갈 수 있다면 해당 좌표에 숫자를 넣고, sudoku(idx+1)을 호출한다.

4. 재귀함수를 반복하여 스도쿠가 모두 완성이 되었으면 출력하고, 시스템을 종료한다.

주의할 점

• sudoku() 가 리턴되고 난 후, arr[tmp[0]][arr[tmp[1] = 0; 을 무조건 해주어야 한다. 그렇지 않으면, 이전 함수로 돌아갈 때 0이 아닌 숫자가 남겨져 있는 채로 return 될 수 있다.

코드

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

public class Main {

    static int[][] arr = new int[9][9];
    static ArrayList<int[]> points;

    static public boolean check(int row, int col, int value) {
        
        //같은 열이나 같은 행에서 같은 숫자가 있는지 체크
        for (int idx = 0; idx < 9; idx++) {
            if (arr[row][idx] == value || arr[idx][col] == value) {
                return false;
            }
        }

        //3x3 정사각형 안에 같은 숫자가 있는지 체크
        int tmpRow = (row / 3) * 3;
        int tmpCol = (col / 3) * 3;

        for (int i = tmpRow; i < tmpRow+3; i++) {
            for (int j = tmpCol; j < tmpCol+3; j++) {
                if (arr[i][j] == value) {
                    return false;
                }
            }
        }

        return true;
    }

    static public void sudoku(int idx) {

        if (idx == points.size()) {

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++)
                    sb.append(arr[i][j] + " ");
                sb.append("\n");
            }
            System.out.println(sb);

            System.exit(0);
        }

        int[] tmp = points.get(idx);

        for (int k = 1; k <= 9; k++) {
            if (check(tmp[0], tmp[1], k)) {
                arr[tmp[0]][tmp[1]] = k;
                sudoku(idx + 1);
            }
            arr[tmp[0]][tmp[1]] = 0;
        }

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        points = new ArrayList<>();

        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                int n = Integer.parseInt(st.nextToken());
                arr[i][j] = n;
                if (n == 0)
                    points.add(new int[]{i, j});
            }
        }

        sudoku(0);

    }
}

• System.exit(0) : 프로그램을 바로 종료한다.

 

---

다른 풀이 2

스도쿠의 빈 칸 좌표를 따로 저장하지 않고, 재귀함수의 인자로 행, 열 번호를 넘긴다.

로직

1. sudoku(row=0, col=0)을 호출한다. 각각 스도쿠의 행, 열 번호이다.

2. arr[row][col] == 0 이라면 for문으로 1~9까지 해당 좌표에 들어갈 수 있는지 check() 함수를 통해 체크한다.

• 들어갈 수 있다면 해당 좌표에 숫자를 넣고, sudoku(row, col+1)을 호출한다.

3. arr[row][col] == 0 이 아니라면 sudoku(row, col+1)을 호출한다.

4. col == 9 라면 sudoku(row + 1, 0);을 호출한다.

5. 재귀함수를 반복하여 row == 9가 되면, 스도쿠가 모두 완성됨을 의미한다. 스도쿠를 출력하고, 시스템을 종료한다.

주의할 점

• arr[row][col] == 0 이라면 반복문이 끝난 후 arr[row][col] = 0; 을 하고 리턴해주어야 한다. 그렇지 않으면, 이전 함수로 돌아갈 때 0이 아닌 숫자가 남겨져 있는 채로 return 될 수 있다.

코드

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

public class Main {

    static int[][] arr = new int[9][9];

    static public boolean check(int row, int col, int value) {

        //같은 열이나 같은 행에서 같은 숫자가 있는지 체크
        for (int idx = 0; idx < 9; idx++) {
            if (arr[row][idx] == value || arr[idx][col] == value) {
                return false;
            }
        }

        //3x3 정사각형 안에 같은 숫자가 있는지 체크
        int tmpRow = (row / 3) * 3;
        int tmpCol = (col / 3) * 3;

        for (int i = tmpRow; i < tmpRow+3; i++) {
            for (int j = tmpCol; j < tmpCol+3; j++) {
                if (arr[i][j] == value) {
                    return false;
                }
            }
        }

        return true;
    }

    static public void sudoku(int row, int col) {

        if (col == 9) {
            sudoku(row + 1, 0);
            return;
        }

        if (row == 9) {

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++)
                    sb.append(arr[i][j] + " ");
                sb.append("\n");
            }
            System.out.println(sb);

            System.exit(0);
        }

        if (arr[row][col] == 0) {
            for (int k = 1; k <= 9; k++) {
                if (check(row, col, k)) {
                    arr[row][col] = k;
                    sudoku(row, col + 1);
                }
            }
            arr[row][col] = 0;
            return;
        }

        sudoku(row, col+1);

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        sudoku(0, 0);
    }
}

 

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