자바(Java) 백준 4574 스도미노쿠 풀이

문제

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

4574번: 스도미노쿠

풀이

dfs 문제인데 조건이 생각보다 까다로워서 코드 작성하는데 시간이 좀 걸렸습니다..
제가 이 문제를 푼 과정은 다음과 같습니다.

• 도미노를 체크해줄 2차원 배열이 필요합니다.
  • visitedDomino[a][b]에서 a와 b는 도미노에 들어있는 숫자를 의미합니다.
  • visitedDomino[b][a]도 체크해줍니다.
• 먼저 입력으로 받은 도미노와 숫자들을 2차원 배열에 값을 입력해줍니다.
• dfs를 통하여 0 ~ 81 까지의 값을 탐색합니다.
  • 이 값은 좌표를 오른쪽, 아래 순서대로 차례대로 탐색하기 위합입니다.
• 첫 번째 좌표가 값이 0이라면 1 ~ 9 까지의 숫자중에서 어떤게 들어갈 수 있는지 체크합니다.
• 그리고 가로와 세로의 도미노를 만들어서 두번째 좌표도 조건에 성립하는지 확인합니다.
• 탐색을 다 마치고 idx의 값이 81이 되면 스도쿠가 완성되었으므로 값을 출력합니다.

코드가 복잡해서 잘 설명하지는 못한 거 같은데 자세한 내용은 코드안의 주석을 참고해주시면 됩니다.

코드

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

public class Main {

    private static int n;
    private static boolean[][] visitedDomino;
    private static int[][] board;
    private static int[] dx = {1, 0};
    private static int[] dy = {0, 1};
    private static int cnt = 1;
    public static boolean flag;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            visitedDomino = new boolean[10][10];
            board = new int[9][9];
            n = Integer.parseInt(br.readLine());

            // n 입력이 0이면 루프문 탈출
            if (n == 0) {
                break;
            }

            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                char[] lu = st.nextToken().toCharArray();
                int v = Integer.parseInt(st.nextToken());
                char[] lv = st.nextToken().toCharArray();

                // 해당 도미노가 사용되었는지 u와 v를 통해 체크합니다.(역순 포함)
                visitedDomino[u][v] = true;
                visitedDomino[v][u] = true;
                // 아스키 코드를 사용하여 좌표를 2차원 배열의 인덱스로 변환합니다.
                board[lu[0] - 65][Character.getNumericValue(lu[1]) - 1] = u;
                board[lv[0] - 65][Character.getNumericValue(lv[1]) - 1] = v;
            }

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i < 10; i++) {
                char[] point = st.nextToken().toCharArray();
                board[point[0] - 65][Character.getNumericValue(point[1]) - 1] = i;
            }
            flag = false;
            dfs(0);
            cnt++;
        }
    }

    public static void dfs(int idx)  {
        // 스도미노쿠를 완성했다면 출력합니다.
        if (idx == 81) {
            // flag는 해당 퍼즐이 출력 된적이 있는지 확인합니다.
            if (flag) {
                return;
            }
            flag = true;
            System.out.printf("Puzzle %d%n", cnt);
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(board[i][j]);
                }
                System.out.println();
            }
            return;
        }

        // idx를 9 * 9 좌표로 변환합니다.
        int x = idx / 9;
        int y = idx % 9;

        // 해당 좌표에 값이 있는 경우 다음 좌표로 넘어갑니다.
        if (board[x][y] != 0) {
            dfs(idx + 1);
            return;
        }

        for (int i = 1; i <= 9; i++) {
            if (isPosNum(x, y, i)) {
                // idx에 따라 순서대로 탐색하므로 해당 좌표에서 오른쪽, 아랫쪽에 숫자가 포함되는 도미노만 사용합니다.
                for (int d = 0; d < 2; d++) {
                    int newX = x + dx[d];
                    int newY = y + dy[d];
                    // 두 번째 좌표가 스도쿠를 벗어나는지 혹은 숫자가 이미 있는지 확인
                    if (newX >= 9 || newY >= 9 || board[newX][newY] != 0) {
                        continue;
                    }
                    for (int j = 1; j <= 9; j++) {
                        // 도미노 안의 숫자가 다르고, 사용하지 않은 도미노이고, 해당 좌표에 숫자 j를 쓸 수 있다면 다음점을 탐색
                        if (i != j && !visitedDomino[i][j] && isPosNum(newX, newY, j)) {
                            board[x][y] = i;
                            board[newX][newY] = j;
                            visitedDomino[i][j] = true;
                            visitedDomino[j][i] = true;
                            dfs(idx + 1);
                            board[x][y] = 0;
                            board[newX][newY] = 0;
                            visitedDomino[i][j] = false;
                            visitedDomino[j][i] = false;
                        }
                    }
                }
            }
        }
    }

    // 스도쿠 규칙에 따라 해당 숫자를 사용할 수 있는지 확인합니다.
    public static boolean isPosNum(int x, int y, int num) {
        for (int i = 0; i < 9; i++) {
            // 세로에 같은 숫자가 있는지 확인
            if (board[i][y] == num) {
                return false;
            }
            // 가로에 같은 숫자가 있는지 확인
            if (board[x][i] == num) {
                return false;
            }
        }

        int startX = (x / 3) * 3;
        int startY = (y / 3) * 3;
        // 해당 좌표가 포함되는 3 * 3 네모 안에 같은 숫자가 있는지 확인
        for (int i = startX; i < startX + 3; i++) {
            for (int j = startY; j < startY + 3; j++) {
                if (board[i][j] == num) {
                    return false;
                }
            }
        }

        return true;
    }
}