[BOJ/Java] 2580. 스도쿠

[BOJ/Java] 2580. 스도쿠

 

2580번: 스도쿠

---

문제 해석

이 문제는 9x9 크기의 스도쿠 판에서 빈 칸을 채우는 방법에 대해 다룬다. 각 행, 열, 그리고 3x3 크기의 박스 안에 1부터 9까지의 숫자가 중복 없이 등장해야 한다. 주어진 스도쿠 판에는 일부 숫자가 이미 채워져 있으며, 이를 바탕으로 빈 칸을 올바르게 채워야 한다.

풀이 과정

제출된 Java 코드는 빈 칸의 위치를 추적하고, 가능한 모든 숫자를 시도하여 문제를 해결하는 백트래킹 방식을 사용한다. 여기서 Point 클래스는 빈 칸의 위치를 저장하며, arrayList는 이러한 위치를 모아둔다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No2580;

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

public class Main {
    private static final int SIZE = 9; // 스도쿠의 크기를 상수로 정의
    private static final int BOX_SIZE = 3; // 박스의 크기를 상수로 정의
    private int[][] graph; // 스도쿠 판을 저장할 배열
    private List<Point> arrayList; // 빈 칸의 위치를 저장할 리스트
    private StringBuilder sb = new StringBuilder(); // 결과를 출력하기 위한 StringBuilder

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        graph = new int[SIZE][SIZE];
        arrayList = new ArrayList<>();
        for (int i = 0; i < SIZE; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < SIZE; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 0) arrayList.add(new Point(i, j)); // 빈 칸 위치 추가
            }
        }
        sol(0); // 백트래킹 시작
        bw.write(sb.toString()); // 결과 출력
        bw.flush();
        bw.close();
    }

    private void sol(int depth) {
        if (sb.length() != 0) { // 이미 해결된 경우
            return;
        }

        if (depth == arrayList.size()) { // 모든 빈 칸을 채웠다면
            for (int i = 0; i < SIZE; i++) {
                for (int j = 0; j < SIZE; j++) {
                    sb.append(graph[i][j]).append(" ");
                }
                sb.append("\n");
            }
            return;
        }

        int x = arrayList.get(depth).x;
        int y = arrayList.get(depth).y;
        for (int n = 1; n <= SIZE; n++) {
            if (checkCol(n, x) && checkRow(n, y) && checkBox(n, x, y)) { // 유효한 숫자인 경우
                graph[x][y] = n;
                sol(depth + 1); // 다음 빈 칸으로
                graph[x][y] = 0; // 백트래킹
            }
        }
    }

    // 열, 행, 박스 검사 메소드 생략...

    class Point {
        int x, y;

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

시간 복잡도 분석

이 코드는 모든 빈 칸에 대해 최대 9개의 가능성을 시도한다. 백트래킹을 사용하기 때문에, 최악의 경우 시간 복잡도는 O(9^n)가 될 수 있다. 여기서 n은 빈 칸의 수이다.

느낀점

스도쿠 문제는 백트래킹으로 해결하는 전형적인 문제 중 하나다. 이 문제를 통해 백트래킹 알고리즘의 효율적인 사용법과 재귀 호출의 처리 방식에 대해 더 잘 이해할 수 있었다. 또한, 스도쿠 판의 유효성을 검증하는 다양한 메소드를 구현함으로써 문제 해결 능력을 향상시킬 수 있었다.