[BOJ_4574] 스도미노쿠 (java)

문제링크

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

4574번: 스도미노쿠

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 재귀, 브루트포스, 백트래킹

스도미노쿠는 스도쿠 + 도미노를 의미하는 게임이다. 스도쿠의 규칙을 지켜주며, 도미노(2개의 쌍으로 이루어진 값)을 놓아주어 스도쿠를 풀어주는 문제이다. 도미노는 $(1,2), (1,3) (1,4) ... (7,8) (7,9) (8,9)$ 까지 1부터 9까지의 모든 값의 쌍으로  이루어져 있다. 그런데 $(1,2)$와 $(2,1)$은 같은 것으로 처리하게 된다. 이러한 쌍을 모두 한번씩만 사용해서 문제를 해결해 주는 것이다. 이러한 쌍은 36개가 나오게 된다.

 

초기에 몇개의 도미노를 놓아주고 그리고 1부터 9까지의 값을 적절한 위치에 놓아주는 것으로 문제가 시작된다. 놓아주는 도미노의 개수는 최소 10개이므로 최악의 경우 26개의 도미노를 놓아주어야 한다. 26개의 도미노를 놓는 방법은 8가지 이므로 모든 경우를 해보는건 사실상 불가능 하다. 하지만 스도쿠는 조건으로 굉장히 많은 값들을 걸러낼 수 있으므로 백트래킹을 해서 문제를 해결할 수 있을 것 같다는 기대로 구현을 하였다.

• 각 행에는 1부터 9까지 숫자가 하나씩 있어야 한다.
• 각 열에는 1부터 9까지 숫자가 하나씩 있어야 한다.
• 3×3크기의 정사각형에는 1부터 9가지 숫자가 하나씩 있어야 한다.

스도쿠의 이러한 특징을 고려하여 특정 칸에 들어갈 수 있는 수를 판단할 수 있다. 나는 문제를 해결하기 위해 위 3가지 조건을 고려하여 해당 칸에 들어올 수 있는 값들을 ArrayList에 넣어 return하여주는 checkInputValue() 메소드를 만들어주었다. 

 

그리고 특정 도미노가 들어갔는지 여부를 확인하기 위해 Hash Map을 사용하였다. Hash Map을 사용한 이유는 Hash함수를 사용하여 조회를 하면 상수시간으로 특정 도미노가 사용되었는지 알 수 있기 때문이다. (물론 해쉬 테이블을 사용해도 된다.)

 

재귀함수가 종료되는 순간은 모든 스도쿠 판을 채웠을 경우이다. 

 

구현코드

package boj_4574;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        int puzzleCount = 1;
        while((n = sc.nextInt()) != 0){
            int[][] board = new int[9][9];
            Map<String, Boolean> map = new HashMap<>();
            for(int i = 0; i < n; i++){
                int num1 = sc.nextInt();
                String location1 = sc.next();
                board[location1.charAt(0)-'A'][location1.charAt(1)-'1'] = num1;

                int num2 = sc.nextInt();
                String location2 = sc.next();
                board[location2.charAt(0)-'A'][location2.charAt(1)-'1'] = num2;
                map.put(Math.min(num1,num2) + "" +Math.max(num1,num2),true);
            }
            for(int i = 1; i <10; i++){
                String location = sc.next();
                board[location.charAt(0)-'A'][location.charAt(1)-'1'] = i;
            }
            solve(board,map,0,0);


            System.out.println("Puzzle " + puzzleCount++);
            for(int i = 0; i < 9; i++){
                for(int j = 0; j < 9; j++){
                    System.out.print(board[i][j]);
                }
                System.out.println();
            }
        }
    }

    public static boolean solve(int[][] board, Map<String,Boolean> map,int x, int y){
        if(x == 9){
            return true;
        }
        if(board[x][y] != 0){
            return solve(board,map,y+1 == 9 ? x+1 : x,(y+1)%9);
        }
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};

        ArrayList<Integer> checkArr = checkInputValue(board, x, y);
        if(checkArr.size() == 0)
            return false;
        for(int i = 0; i < checkArr.size(); i++){
            int inputValue = checkArr.get(i);
            board[x][y] = inputValue;
            for(int idx = 0; idx < 4; idx++){
                int nextX = x+dx[idx];
                int nextY = y+dy[idx];
                if(nextX < 0 || nextX > 8 || nextY < 0 || nextY > 8)
                    continue;
                if(board[nextX][nextY] != 0)
                    continue;

                ArrayList<Integer> nextCheckArr = checkInputValue(board, nextX, nextY);
                if(nextCheckArr.size() == 0)
                    break;
                for(int j = 0; j < nextCheckArr.size(); j++){
                    int inputNext = nextCheckArr.get(j);
                    String key = Math.min(inputNext,inputValue) + "" +Math.max(inputNext,inputValue);
                    if(map.containsKey(key)){
                        continue;
                    }
                    map.put(key,true);
                    board[nextX][nextY] = inputNext;
                    if(solve(board,map,y+1 == 9 ? x+1 : x,(y+1)%9))
                        return true;
                    board[nextX][nextY] = 0;
                    map.remove(key);
                }
            }
            board[x][y] = 0;
        }
        return false;
    }

    // 해당 칸에 삽입이 가능한 값들을 모아서 ArrayList에 넣어서 반환
    private static ArrayList<Integer> checkInputValue(int[][] board, int x, int y) {
        ArrayList<Integer> checkArr = new ArrayList<>();
        for(int i = 1; i < 10; i++){
            int j;

            for(j = 0; j < board.length; j++){
                if(board[j][y] == i || board[x][j] == i){
                    break;
                }
            }
            if(j == board.length){
                int xShare = x /3;
                int yShare = y /3;
                boolean isOk = true;
                for(int xIdx = 0; xIdx < 3; xIdx ++){
                    for(int yIdx = 0; yIdx < 3; yIdx++){
                        if(board[xShare*3 + xIdx][yShare*3 + yIdx] == i)
                            isOk = false;
                    }
                }
                if(isOk){
                    checkArr.add(i);
                }
            }
        }
        return checkArr;
    }
}

 

시간복잡도

시간복잡도는 위에서 설명한대로 $O(8^n)$이지만, 백트래킹을 사용하여 적용이 가능한 조건으로만 추려서 해결할 수 있다. (n = 도미노의 개수)

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)