[백준] 2239번 스도쿠 - Java/자바

문제

문제 바로가기

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

---

접근방법

백트래킹 알고리즘을 사용하여 모든 경우를 탐색하면서 답을 찾는 방식으로 풀 수 있다.

현재 선택된 수가 행, 열, 3x3 정사각형 안에서 중복되는 수가 없는지를 잘 체크하는 것이 중요하다.

풀이

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

class Coo {
    int x, y;
    Coo(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int[][] board = new int[9][9];
    static List<Coo> coo = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int i = 0; i < 9; i++) {
            String str = br.readLine();
            for(int j = 0; j < 9; j++) {
                board[i][j] = str.charAt(j) - '0';
                if(board[i][j] == 0) {
                    coo.add(new Coo(i, j));
                }
            }
        }

        dfs(0);
    }

    public static void dfs(int depth) {
        if(depth == coo.size()) {
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) {
                    System.out.print(board[i][j]);
                }
                System.out.println();
            }
            System.exit(0);
        }
        for(int j = 1; j <= 9; j++) {
            if(check(coo.get(depth).x, coo.get(depth).y, j)) {
                board[coo.get(depth).x][coo.get(depth).y] = j;
                dfs(depth + 1);
                board[coo.get(depth).x][coo.get(depth).y] = 0;
            }
        }
    }

    public static boolean check(int x, int y, int num) {
        for(int i = 0; i < 9; i++) {
            if(board[x][i] == num) return false;
            if(board[i][y] == num) return false;
        }
        int tx = x/3 * 3;
        int ty = y/3 * 3;
        for(int j = 0; j < 3; j++) {
            for(int k = 0; k < 3; k++) {
                if(board[tx+j][ty+k] == num)
                    return false;
            }
        }
        return true;
    }
}