알고리즘 풀이 - 백준 4574(스도미노쿠, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

1~9의 숫자의 위치와 도미노의 위치가 주어질 때, 스도쿠를 풀고난 뒤 그 결과를 출력하는 문제

 

 

2. 풀이

 

관련 문제인 스도쿠 문제는 여기서 참조 가능

스도미노쿠는 스도쿠를 풀되 2개의 숫자가 이어진 도미노를 모두 놓아서 해결할 수 있는 경우를 찾는 문제이다. 우선 주어진 도미노와 1~9의 숫자를 스도쿠 상에 위치시키고 사용 가능한 도미노를 위치시켜 전체 문제를 풀 수 있는 경우에 출력을 한다.

 

9x9가 고정이므로 81을 이용해 9로 나누어 행(y) 좌표, 9로 나눈 나머지를 열(x) 좌표로 구할 수 있으며 이를 통해 해당 위치가 0이라면 인접 비어 있는 위치까지 찾아서 도미노를 놓고 해당 위치에 각 숫자가 적절한지 체크하는 과정을 반복한다.

위 과정 중에 다음 재귀의 위치가 81이 되었다면 모든 위치에 숫자가 위치한 것이므로 그 결과를 true로 반환하면 된다.

 

자세한 내용은 코드를 통해 알아보자. 

 

참고로, 스도쿠에서 숫자의 위치가 적절한지를 알아보려면 같은 행, 같은 열, 같은 3x3 정사각형에서 같은 숫자가 있는지를 체크해야 한다.

행과 열은 쉽지만 3x3 정사각형을 체크하는 방법은 아래를 참고하자.

 

각 위치는 위와 같이 index로 지정할 수 있는데, 만약 현재 비어 있는 숫자가 (4, 4)라고 가정해보자.

그러면, 체크해야 할 3x3 정사각형은 (3, 3) ~ (5, 5)까지이다. 여기서 Row / Column의 범위를 제한해주면 된다는 의미이다.

우선 Row 를 점검해보자. Row의 값이 3~5인 경우에는 3~5를 / 0~2인 경우에는 0~2를 / 6~8이면 6~8부분을 점검해야 한다.

어떻게 그 범위를 정할 수 있을까? 0~8까지 각 위치를 3으로 나누어보자. 그러면 아래와 같이 될 것이다.
(0, 0, 0 || 1, 1, 1, || 2, 2, 2)와 같이 나누어질 것이다. 그러면 여기에 3을 곱하면 다시 아래와 같이 된다.
(0, 0, 0 || 3, 3, 3, || 6, 6, 6)이 된다. 즉, 시작할 위치를 지정할 수 있게 된다.

다시 저 값에 2를 더한 위치까지만 모두 체크를 하면 된다. Column도 동일한 방식으로 체크를 할 수가 있게 된다.

 

따라서 (4, 4)를 점검하고자 한다면 (4 / 3 x 3) ~ (4 / 3 x 3) + 2까지, 즉, 3부터 5까지로 각 Row, Column을 제한 시킬 수 있게 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int[][] sudoku;
    
    // 아래, 오른쪽만 체크
    static int[] dy = {1, 0};
    static int[] dx = {0, 1};
    
    // 1~9까지 각 숫자를 조합한 쌍의 도미노의 사용 여부 저장하는 배열
    static boolean[][] domino;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        
        // 몇 번째 퍼즐인지 출력하기 위해 사용되는 변수
        int t = 1;
        
        // 0이 입력되기 전에 지속 반복 수행
        while(true){
            st = new StringTokenizer(br.readLine());
            
            int n = Integer.parseInt(st.nextToken());
            if(n == 0) break;  // 0이 입력되었다면 더 이상의 case는 없으니 break 수행
            sb.append("Puzzle ").append(t).append("\n");
            
            // 스도쿠 숫자와 사용된 도미노를 저장하는 배열 생성
            sudoku = new int[9][9];
            domino = new boolean[10][10];
            
            // 주어진 도미노 타일을 모두 저장시키고 사용된 도미노는 boolean으로 true 저장
            for(int i=0; i < n; i++){
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                String pos1 = st.nextToken();
                sudoku[pos1.charAt(0) - 'A'][pos1.charAt(1) - '1'] = u;
                
                int v = Integer.parseInt(st.nextToken());
                String pos2 = st.nextToken();
                sudoku[pos2.charAt(0) - 'A'][pos2.charAt(1) - '1'] = v;
                
                // 사용된 쌍은 순서를 바꾸어도 이미 사용된 것으로 처리
                domino[u][v] = true;
                domino[v][u] = true;
            }
            
            // 1~9까지의 주어진 숫자를 스도쿠 상에 저장한다.
            st = new StringTokenizer(br.readLine());
            for(int i=1; i <= 9; i++){
                String val = st.nextToken();
                sudoku[val.charAt(0) - 'A'][val.charAt(1) - '1'] = i;
            }
            
            backtrack(0);
            for(int i=0; i < 9; i++){
                for(int j=0; j < 9; j++){
                    sb.append(sudoku[i][j]);
                }
                sb.append("\n");
            }
            t++;
        }
        
        System.out.println(sb);
        br.close();
    }
    
    // 백트래킹을 통해 각 위치에 적절한 숫자를 넣는다.
    private static boolean backtrack(int pos){
    
        // 81이라는 것은 모든 위치에 숫자가 채워진 것이므로 true를 반환
        if(pos == 81) return true;
        
        // 81에서 9를 나누고 나머지를 구하여 전체 위치를 체크할 수 있다.
        int y = pos / 9;
        int x = pos % 9;
        
        // 만약 값이 지정되지 않은 경우만 체크
        if(sudoku[y][x] == 0){
            // 현재와 인접한 위치 2개를 도미노로 놓아야 하므로 같이 체크
            for(int k=0; k < 2; k++){
                int ny = y + dy[k];
                int nx = x + dx[k];
                
                // 위치를 넘었거나 이미 숫자가 있는 경우는 제외한다.
                if(ny < 0 || ny >= 9 || nx < 0 || nx >= 9 || sudoku[ny][nx] != 0) continue;
                
                // 이용 가능한 도미노를 체크
                for(int i=1; i <= 9; i++){
                    for(int j=1; j <= 9; j++){
                        // 같은 숫자이거나 이미 사용된 도미노이면 탐색 지속
                        if(i == j || domino[i][j]) continue;
                        
                        // 도미노의 숫자를 2개의 위치에 모두 놓을 수 있다면
                        if(check(y, x, i) && check(ny, nx, j)){
                            // 그 값을 저장하고 true로 전환하여 도미노 사용 처리
                            sudoku[y][x] = i;
                            sudoku[ny][nx] = j;
                            
                            domino[i][j] = true;
                            domino[j][i] = true;
                            
                            // 다음 위치로 이동
                            if(backtrack(pos+1)) return true;
                            
                            // 위에서 true 반환 되지 않았다면 반복문 지속 탐색 수행
                            domino[i][j] = false;
                            domino[j][i] = false;
                            
                            sudoku[y][x] = 0;
                            sudoku[ny][nx] = 0;
                        }
                    }
                }
            }
        // 이미 값이 있다면 다음 위치로 바로 이동
        } else {
            return backtrack(pos+1);
        }
        
        // true가 위에서 반환되지 않았다면 false 반환
        return false;
    }
    
    // 각 위치에 해당 값을 놓을 수 있는지 체크한다.
    private static boolean check(int y, int x, int n){
        int row = 0;
        int col = 0;
        for(; row < 9; row++){
            if(sudoku[row][x] == n) return false;
        }
        
        for(; col < 9; col++){
            if(sudoku[y][col] == n) return false;
        }
        
        row = (y / 3) * 3;
        col = (x / 3) * 3;
        for(int i=row; i < row+3; i++){
            for(int j=col; j < col+3; j++){
                if(sudoku[i][j] == n) return false;
            }
        }
        return true;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.