21.09.08 기록

백준 알고리즘 2580 풀이

🎆해설(메모리 27.5MB, 시간 504ms로 통과)

-백트래킹을 어떻게 써야하는지 감도 잡지 못해 해설을 봤다.(재귀 함수를 구현하는 것부터가 문제인 것 같다..😥)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B2580 {
    public static int size = 9;
    public static int[][] sudoku = new int[size][size];

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

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

        getSudoku(0,0);
    }

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

        //행이 다 채워진 경우 다음 열로
        if(col == size) {
            getSudoku(row + 1, 0);
            return;
        }

        //열도 모두 채워진 경우 출력 후 종료
        if(row == size) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < size; i++) {
                for(int j = 0; j < size; j++) {
                    sb.append(sudoku[i][j]).append(' ');
                }
                sb.append('\n');
            }
            System.out.println(sb);
            System.exit(0);
        }

        //값이 0일 때 가능한 수 탐색
        if(sudoku[row][col] == 0) {
            for(int i = 1; i <= size; i++) {
                if(isPossible(row, col, i)) {//sudock[row][col] = i 가 가능한지? (중복 검사)
                    sudoku[row][col] = i;
                    getSudoku(row, col+1);
                }
            }
            sudoku[row][col] = 0;
            return;
        }

        getSudoku(row, col + 1);
    }

    public static boolean isPossible(int row, int col, int val) {
        //같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사
        for(int i = 0; i < size; i++) {
            if(sudoku[row][i] == val) {
                return false;
            }
        }

        //같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
        for(int i = 0; i < size; i++) {
            if(sudoku[i][col] == val) {
                return false;
            }
        }

        //3*3 칸에 중복되는 원소가 있는지 검사
        int setRow = (row / 3) * 3;
        int setCol = (col / 3) * 3;

        for(int i = setRow; i < setRow+3; i++) {
            for(int j = setCol; j < setCol+3; j++) {
                if(sudoku[i][j] == val) {
                    return false;
                }
            }
        }
        return true;
    }
}