[백준] 2580 : 스도쿠

문제 출처:https://www.acmicpc.net/problem/2580

---

문제

---

시도

 

문제의 카테고리는 백트래킹으로 분류되었지만 일단 재귀로 먼저 시도해보았다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.HashSet;
import java.util.stream.Collectors;

public class Main {

    private static int zeros = 0;
    private static HashSet<Integer> set;
    // 입력 : 9 X 9 개의 수 입력 (0 ~ 9)
    private static int[][] sudoku = new int[9][9];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int tmp;
        // 1. BufferedReader와 StringTokenizer를 통해 sudoku 채우기
        for(int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < 9; j++) {
                tmp = Integer.parseInt(st.nextToken());

                if(tmp == 0) zeros++;
                sudoku[i][j] = tmp;
            }
        }

        // 2. [0][0] 부터 [9][9]를 순회하며 값이 0인 경우,
        // 가로/세로/3x3을 순회하며 적합한 값 찾기
        while(zeros > 0) {
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) {
                    if(sudoku[i][j] != 0) continue;

                    set = new HashSet<>();
                    set.addAll(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
                    if(checkX(i) == 1) replaceZero(i, j);
                    else if(checkY(j) == 1) replaceZero(i, j);
                    else if(check3x3(i, j) == 1) replaceZero(i, j);
                }
            }
        }
        // 3. 2의 과정을 모든 0이 사라질 때까지 적용하기

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                sb.append(sudoku[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }

    private static int checkX(int x) {
        for(int i = 0; i < 9; i++)
            set.remove(sudoku[x][i]);

        return set.size();
    }

    private static int checkY(int y) {
        for(int i = 0; i < 9; i++)
            set.remove(sudoku[i][y]);

        return set.size();
    }

    private static int check3x3(int x, int y) {
        int stdX = x/3;
        int stdY = y/3;

        for(int i = stdX; i < 3 * (stdX+1); i++) {
            for(int j = stdY; j < 3 * (stdY+1); j++) {
                set.remove(sudoku[i][j]);
            }
        }

        return set.size();
    }

    private static void replaceZero(int i, int j) {
        sudoku[i][j] = set.stream().collect(Collectors.toList()).get(0);
        zeros--;
    }
}

 

이 코드를 시도해보는 데만도 많은 40분 가량의 시간과 자원이 소모되었다

그 중 주의해야 했던 점은

1. StringBuilder로 String 합칠 시 '' (character)를 사용하면 integer 값이 ASCII 값으로 변환됨
2. set을 1~9의 값으로 초기화할 때, .addAll(Arrays.asList(1,2,3,4,5,6,7,8,9));를 사용한 것
3. set의 크기가 1이 됐을 대 해당 값만 추출하기 위해 .stream().collect(Collectors.toList()).get(0);으로 꺼내기 (링크)

였지만, 애초에 시간초과로 인해 실패했다...

 

---

풀이

 

다른 사람의 풀이를 참고하여 파악한 차이점은

  나는 값 0이 있는 자리에 한 번 머물며 적합한 값이 있는지 확인하고 없다면 다음을 기약하며 넘어간다면

  정석 풀이는 값 0이 있는 자리에서 1~9의 값을 모두 대입해보며 값을 찾을 때까지 넘어가지 않았다는 점이다.

 

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

public class Main {

    // 입력 : 9 X 9 개의 수 입력 (0 ~ 9)
    private static int[][] arr = new int[9][9];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 1. BufferedReader와 StringTokenizer를 통해 arr 채우기
        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < 9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        sudoku(0, 0);
    }

    public static void sudoku(int row, int col) {
        if (col == 9) {
            sudoku(row + 1, 0);
            return;
        }

        if (row == 9) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(arr[i][j]).append(' ');
                }
                sb.append('\n');
            }
            System.out.println(sb);
            // 출력 뒤 시스템을 바로 종료하여 재귀 방지
            System.exit(0);
        }

        if (arr[row][col] == 0) {
            for (int i = 1; i <= 9; i++) {
                if (possibility(row, col, i)) {
                    arr[row][col] = i;
                    sudoku(row, col + 1);
                }
            }
            arr[row][col] = 0;
            return;
        }

        sudoku(row, col + 1);
    }

    public static boolean possibility(int row, int col, int value) {

        for (int i = 0; i < 9; i++) {
            if (arr[row][i] == value) return false;
        }

        for (int i = 0; i < 9; i++) {
            if (arr[i][col] == value) return false;
        }

        int x = 3 * (row / 3);
        int y = 3 * (col / 3);

        for (int i = x; i < x + 3; i++) {
            for (int j = y; j < y + 3; y++) {
                if(arr[i][j] == value) return false;
            }
        }

        return true;
    }
}

 

코드를 따라 쳐보면서 굉장히 쉽게 이해가 되고, 한번 값을 대입해보고 틀리다면 다시 돌아가는 backtracking 까지 적용된 인상적이라고 여겼는데, IntelliJ에서 실행해보니 뭔가 이상했다.

 

내가 처음 작성한 코드보다 결과를 내놓는 속도가 느렸던 것이다. 뭔가 쎄해서 백준에 제출해봤는데 똑같이 시간초과가 떴다. 

 

몇 번이고 코드를 수정해본 결과 possibility 메서드를 아래와 같이 바꿨을 때 정답을 인정 받았지만, 지금도 '그래서 이게 뭐가 문젠데'라는 생각 밖에 안들 정도로 어이가 없다. 

    public static boolean possibility(int row, int col, int value) {
        // 같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사
        for (int i = 0; i < 9; i++) {
            if (arr[row][i] == value) {
                return false;
            }
        }
        // 같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
        for (int i = 0; i < 9; i++) {
            if (arr[i][col] == value) {
                return false;
            }
        }
        // 3*3 칸에 중복되는 원소가 있는지 검사
        int set_row = (row / 3) * 3; // value가 속한 3x3의 행의 첫 위치
        int set_col = (col / 3) * 3; // value가 속한 3x3의 열의 첫 위치
        for (int i = set_row; i < set_row + 3; i++) {
            for (int j = set_col; j < set_col + 3; j++) {
                if (arr[i][j] == value) {
                    return false;
                }
            }
        }


            return true;
        }
    }

 

참고 출처: https://st-lab.tistory.com/119

---

알게 된 점

 - 진짜 어이 없는 문제다..