[백준 JAVA] 2239 스도쿠 풀이

[문제 링크] 자바 2239 스도쿠 java 풀이 백트랙킹, 구현

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

2239번: 스도쿠

 

[생각 흐름]

여러가지가 있다면 사전식 출력을 원하고 있어서 1~9까지 모든 숫자를 가능하면 넣어 보는 식으로 해결했다.

먼저 칸이 빈칸이라면 arraylist에 넣어두고 DFS를 첫 빈칸부터 시작하도록 하였다.

현재 채울 칸의 가로와 세로, 정사각형 칸을 비교하고 가능하면 넣었다.

그리고 다음 빈칸 을 진행할 수 있도록 하였다.

만약 다음칸에서 채워지지 않아서 돌아오면 원래 값으로 돌리고 다시 가능한 다른 수를 넣을 수 있게 하였다.

만약 한번이라도 출력하였다면 totalF를 변경하여 더 이상 동작하지 않고 멈추도록 구성하였다.

 

 

[코드]

import javax.swing.*;
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main{
    static int[][] arr;
    static ArrayList<Point> list = new ArrayList<Point>(); //채워지지 않은 배열
    static boolean totalF = false; //스도쿠가 한번 다 채워지면 멈추게하는 용도

    private static void dfs(int n) {
        if (n == list.size()) { //모든 칸이 채워졌다면
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++)
                    sb.append(arr[i][j]);
                sb.append("\n");
            }
            System.out.print(sb);
            totalF = true; //더 이상 탐색하지 못하도록
            return;
        }
        
        Point temp = list.get(n);
        for (int i = 1; i < 10; i++) {

            boolean flag = true;
            //가로
            for (int p = 0; p < 9; p++) if (arr[temp.x][p] == i) flag = false;
            if (!flag) continue;
            //세로
            for (int p = 0; p < 9; p++) if (arr[p][temp.y] == i) flag = false;
            if (!flag) continue;
            //사각형
            for (int p = temp.x / 3 * 3; p < (temp.x / 3 + 1) * 3; p++) {
                for (int q = temp.y / 3 * 3; q < (temp.y / 3 + 1) * 3; q++)
                    if (arr[p][q] == i) flag = false;
            }
            if (!flag) continue;

            arr[temp.x][temp.y] = i; //i로 채운다
            dfs(n + 1); //다음 칸 채우기
            if(totalF) break; //만약 한번 출력되었다면 멈춘다
            arr[temp.x][temp.y] = 0; //돌아온 경우 다시 값 복원
        }
        return;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = new int[9][9];
        for (int i = 0; i < 9; i++) {
            String temp = br.readLine();
            for (int j = 0; j < 9; j++) {
                arr[i][j] = Integer.parseInt(temp.substring(j, j + 1));
                if (arr[i][j] == 0) list.add(new Point(i, j)); //칸이 빈 경우 list에 추가
            }
        }
        dfs(0);

    }
}