[백준 2580] 스도쿠 (Java)

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

2580번: 스도쿠

접근 방식

복잡해 보였지만 백트래킹이라는 큰 틀 안에서 해결 가능했다.

우선 스도쿠 판에서 0인 부분의 좌표를 List로 담았다.

 

첫번째 좌표를 가져와 해당 숫자가 조건을 만족한다면 그 숫자로 값을 채우고

다음 좌표를 가져와 채워나갔다.

 

조건은 크게 3가지가 있다.

1. 해당 좌표가 속해있는 행에서 숫자가 중복되지 않아야 한다.

2. 해당 좌표가 속해있는 열에서 숫자가 중복되지 않아야 한다.

3. 해당 좌표가 속해있는 사각형에서 숫자가 중복되지 않아야 한다.

 

조건을 모두 만족하는 경우에만 백트래킹을 진행하였고,

조건을 만족하지 못한다면 진행하고 있던 dfs는 포기하고 되돌아가 다시 탐색을 한다.

마지막 좌표까지 모두 방문한 경우 모든 좌표가 채워졌으므로 이를 출력한다.

 

 

[tip]

백준에서 제공하는 테스트 코드가 1개 뿐이라 구현한 코드를 좀 더 테스트해보고 싶다면 스도쿠 문제를 구글링하여 시도해보면 좋다.Go

 

 

최종 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
    private static final int SUDOKU_SIZE = 9;
    private static List<Point> targets;
    private static int[][] sudoku = new int[SUDOKU_SIZE][SUDOKU_SIZE];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        targets = new ArrayList<>(); // 입력받은 스도쿠 판에서 비어있는 좌표(0인 경우)를 담아둠.

        for (int i = 0; i < SUDOKU_SIZE; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < SUDOKU_SIZE; j++) {
                sudoku[i][j] = Integer.parseInt(input[j]);

                if (sudoku[i][j] == 0) {
                    targets.add(new Point(i, j));
                }
            }

        }

        findAnswer(0);
    }

    private static void findAnswer(int count) throws IOException {
        if (count == targets.size()) {
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            for (int i = 0; i < SUDOKU_SIZE; i++) {
                StringBuilder output = new StringBuilder();

                for (int j = 0; j < SUDOKU_SIZE; j++) {
                    output.append(sudoku[i][j]).append(" ");
                }

                bw.write(output.toString().trim() + "\n");
            }

            bw.flush();
            bw.close();
            System.exit(0); // 결과 한개만 출력하면 되기 때문에 출력 후 프로세스 종료
        }

        for (int j = 1; j <= 9; j++) {
            int row = targets.get(count).x;
            int column = targets.get(count).y;

            if (isAbleInRow(j, row) && isAbleInColumn(j, column) && isAbleInCircle(j, row, column)) {
                sudoku[row][column] = j;
                findAnswer(count + 1);
                sudoku[row][column] = 0;
            }
        }
    }

	// 행 기준 순자가 겹치지 않는지 확인
    private static boolean isAbleInRow(int number, int row) {
        for (int i = 0; i < SUDOKU_SIZE; i++) {
            if (number == sudoku[row][i]) return false;
        }

        return true;
    }

	// 열 기준 순자가 겹치지 않는지 확인
    private static boolean isAbleInColumn(int number, int column) {
        for (int i = 0; i < SUDOKU_SIZE; i++) {
            if (number == sudoku[i][column]) return false;
        }

        return true;
    }

	// 정사각형 기준 순자가 겹치지 않는지 확인
    private static boolean isAbleInCircle(int number, int row, int column) {
        int x_start = getStartSpot(row);
        int y_start = getStartSpot(column);

        for (int i = x_start; i < x_start + 3; i++) {
            for (int j = y_start; j < y_start + 3; j++) {
                if (number == sudoku[i][j]) return false;
            }
        }

        return true;
    }

    private static int getStartSpot(int number) {
        int spot = 0;

        switch (number / 3) {
            case 0:
                spot = 0;
                break;
            case 1:
                spot = 3;
                break;
            case 2:
                spot = 6;
                break;
        }

        return spot;
    }


    static class Point {
        private int x;
        private int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}