[Gold IV] 스도쿠 - 2580

문제 링크

성능 요약

메모리: 22056 KB, 시간: 424 ms

분류

백트래킹(backtracking)

문제 설명

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

풀이

스도쿠의 채워야 할 공간들의 좌표를 ArrayList에 담고, 1~9까지 대입해가면서 넣을 수 있는 수(가로, 세로, 3x3 다 가능한지)면,
채워넣고 다음 채워야 할 좌표로 이동 (depth +1).

depth는 스도쿠에서 넣어야 할 공백의 순서 (ArrayList의 Index)대로 진행하면서, 각 공백에 넣을 수 있는 숫자들을 넣어가면서 진행하다가
전체 공백이 다 채워지는 순간, 출력하고 System.exit(0) 으로 종료한다. (문제 조건에 경우가 여러개면 하나만 출력하라고 했다)

개인적으로 3\*3의 검증을 얼마나 깔끔하게 구하는지가 관건이었다.

코드

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

public class Main {

    //스도쿠 공백의 좌표를 담을 Node
    public static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    //전체 스도쿠
    static int[][] graph = new int[9][9];
    //공백의 좌표들을 담을 List
    static ArrayList<Node> targets = new ArrayList<>();
    //공백의 총 길이
    static int size;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 9; i++) {
            String[] strs = br.readLine().split(" ");
            for (int j = 0; j < 9; j++) {
                graph[i][j] = Integer.parseInt(strs[j]);
                if(graph[i][j] == 0) targets.add(new Node(i, j));
            }
        }
        size = targets.size();

        dfs(0);
    }

    static void dfs(int depth) {
        //depth가 0부터 시작하기 때문에, 공백의 사이즈에 도달하면 모든 공백이 채워진 것이다.
        if (depth == size) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(graph[i][j] + " ");
                }
                System.out.println();
            }
            //출력하고 종료
            System.exit(0);
        }

        //지금 공백을 꺼낸다. (depth가 공백 순서)
        Node now = targets.get(depth);
        int nowX = now.x;
        int nowY = now.y;
        //1~9까지 공백에 들어갈 수 있는 수를 구분하여 넣어서 반복
        for (int i = 1; i <= 9; i++) {
            if (possibility(now, i)) {
                graph[now.x][now.y] = i;
                dfs(depth + 1);
                graph[now.x][now.y] = 0;
            }
        }
    }

    //스도쿠 공백 수가 들어갈 수 있는 수인지 검증
    static boolean possibility(Node now, int value) {
        //가로
        for (int i = 0; i < 9; i++) {
            if (Math.abs(graph[now.x][i]-value)==0) {
                return false;
            }
        }
        //세로
        for (int i = 0; i < 9; i++) {
            if (Math.abs(graph[i][now.y]-value) == 0) {
                return false;
            }
        }

        int nowX = (now.x / 3) * 3;
        int nowY = (now.y / 3) * 3;
        //3x3
        for (int i = nowX; i < nowX + 3; i++) {
            for (int j = nowY; j < nowY + 3; j++) {
                if (Math.abs(graph[i][j]-value) == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

저작자표시 비영리 변경금지