[백준 2580] 스도쿠(Java)

문제 링크 : https://www.acmicpc.net/problem/2580

이 문제는 백트래킹 방식을 이용하여 문제를 풀 수 있습니다. 0으로 입력받은 좌표값에 1부터 9까지 차례대로 넣어보고 스도쿠의 조건, 즉 새롭게 추가한 숫자가 현재 가로줄, 세로줄, 그리고 사각형에 존재하는지를 확인하여 존재하지 않는다면 다음 좌표를 탐색하는 방식으로 하나하나 나아가면 됩니다. 모든 좌표를 치환했을 경우 출력하고 함수를 종료하면 됩니다.

제가 헤맸던 부분은 크게 2가지 입니다. 우선 입력할 때마다 체크하는 것이 아니라 일단 입력받은 후 모든 좌표값을 입력받은 상태에서 체크를 진행하였고, 따라서 현재 해당 숫자가 존재하는지에 대한 로직이 아닌 가로줄, 세로줄, 그리고 사각형의 숫자의 합이 45일 경우로 체크를 진행했습니다. 이 경우 값이 중복되더라도 합이 45만 된다면 정상적으로 수행되므로 잘못된 방법입니다.

또한 출력 후 리턴 대신 System.exit(0);을 실행하여 프로그램을 아예 종료시켜야 합니다. 만약 리턴을 진행했을 경우 다음 가능성이 있는 출력이 이어서 진행되기 때문에 출력 양식에 어긋나 잘못된 풀이가 됩니다.

다음은 작성 코드입니다.

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

class Pair{
    int y;
    int x;

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

public class Main{
    static int[][] sudoku = new int[9][9];
    static ArrayList<Pair> req = new ArrayList<>();

    static void printSudoku(){
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                sb.append(sudoku[i][j]);
                sb.append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static boolean isPossibleNum(int y, int x, int num){
        int y_start =  (y/3)*3;
        int x_start = (x/3)*3;

        for(int i=0;i<9;i++){
            // 가로 기준 탐색
            if(sudoku[y][i]==num) return false;

            // 세로 기준 탐색
            if(sudoku[i][x]==num) return false;

            // 사각형 기준 탐색
            if(sudoku[y_start + i/3][x_start + i%3]==num) return false;
        }
        return true;
    }

    static void backtracking(int cnt){
        if(cnt == req.size()){
            printSudoku();
            System.exit(0);
        }

        int y = req.get(cnt).y;
        int x = req.get(cnt).x;
        for(int j=1;j<=9;j++){
            if(isPossibleNum(y,x,j)){
                sudoku[y][x] = j;
                backtracking(cnt+1);
                sudoku[y][x] = 0;
            }
        }
    }

    public static void main(String[] args) throws Exception{
        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++){
                sudoku[i][j] = Integer.parseInt(st.nextToken());
                if(sudoku[i][j] == 0) req.add(new Pair(i,j));
            }
        }

        backtracking(0);
    }
}