[알고리즘] 백준 > #2580. 스도쿠

문제링크

백준 #2580. 스도쿠

풀이방법

스도쿠 풀이방법을 떠올려 봤을 때 바로 백트래킹이라는 생각이 들었다. 초등학생, 중학생 때 스도쿠를 풀 땐 몰랐지만 그때도 백트래킹을 머리로 하며 풀었던 거였다..!

백트래킹이라는 풀이방법까지는 쉽게 접근했는데 이걸 매번 특정 칸이 속하는 행, 열, 박스에 없는 수를 확인하는게 비효율적이라고 생각했다. 그래서 각 행, 열, 박스에 대한 visited 배열을 뒀다. 행, 열은 0, 1, ..., 8의 키 값을 가져 이차원배열을 이용해 visited를 쉽게 구현할 수 있지만 박스는 (0, 0), (0, 1), (0, 2), (1, 0) .. 이런 식으로 키 값을 가지기 때문에 HashMap을 이용했다.

JavaFx에서 제공하는 Pair 객체를 이용하면 바로 해결할 수 있지만 Custom Key Class를 구현했다. 이름은 Pair로 동일하게 했다. *HashMap은 내부적으로 hashCode(), equals() 메서드를 사용한다. 따라서, Key 값으로 Pair 클래스를 활용하기 위해 각 메서드를 재정의 해야 했다. hashCode()는 내부에서 Objects.hash()를 사용했다. 해당 메서드는 같은 매개변수를 전달하면 같은 리턴값을 주기 때문이다. 또, equals()에서는 각 값을 비교하는 방식으로 구현했다. 끝!

hashCode(): identify bucket
equals(): check that the properties values are same
즉, hashCode()를 통해 HashMap Array 내 한 원소인 bucket에 접근, 다른 키 값임에도 같은 hash를 가져 같은 bucket에 속할 수 있기 때문에 그 안을 돌며 equals()를 이용해 그 key인지 확인

코드

import java.util.*;

public class BOJ2580 {

    static private int[][] sudoku = new int[9][9];
    static private LinkedList<Integer> holeY = new LinkedList<>();
    static private LinkedList<Integer> holeX = new LinkedList<>();

    static private final int HOLE = 0;

    static private HashMap<Integer, boolean[]> rowVisited = new HashMap();
    static private HashMap<Integer, boolean[]> colVisited = new HashMap();
    static private HashMap<Pair, boolean[]> boxVisited = new HashMap();

    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = sc.nextInt();

                if (sudoku[i][j] == HOLE) {
                    holeY.add(i);
                    holeX.add(j);
                }
            }
        }
        initVisiteds();

        findSudoku(0);

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

    static private boolean findSudoku(int holeIndex) {
        if (holeIndex == holeX.size()) return true;

        int holeRow = holeY.get(holeIndex);
        int holeCol = holeX.get(holeIndex);

        for (int i = 1; i < 10; i++) {
            if (!rowVisited.get(holeRow)[i] && !colVisited.get(holeCol)[i] && !boxVisited.get(new Pair(holeRow / 3, holeCol / 3))[i]) {
                sudoku[holeRow][holeCol] = i;
                rowVisited.get(holeRow)[i] = colVisited.get(holeCol)[i] = boxVisited.get(new Pair(holeRow / 3, holeCol / 3))[i] = true;

                if (findSudoku(holeIndex + 1)) return true;

                sudoku[holeRow][holeCol] = HOLE;
                rowVisited.get(holeRow)[i] = colVisited.get(holeCol)[i] = boxVisited.get(new Pair(holeRow / 3, holeCol / 3))[i] = false;
            }
        }

        return false;
    }

    static private void initVisiteds() {
        for (int i = 0; i < 9; i++) {
            boolean[] tempVisited = new boolean[10];

            for (int j = 0; j < 9; j++) tempVisited[sudoku[i][j]] = true;
            rowVisited.put(i, tempVisited);
        }
        for (int j = 0; j < 9; j++) {
            boolean[] tempVisited = new boolean[10];

            for (int i = 0; i < 9; i++) tempVisited[sudoku[i][j]] = true;
            colVisited.put(j, tempVisited);
        }
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) boxVisited.put(new Pair(i, j), new boolean[10]);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) boxVisited.get(new Pair(i / 3, j / 3))[sudoku[i][j]] = true;
        }
    }
}

class Pair {
    final int y;
    final int x;

    public Pair(int y, int x) {
        this.y = y;
        this.x = x;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;

        Pair otherObj = (Pair) obj;

        return (this.y == otherObj.y) && (this.x == otherObj.x);
    }

    @Override
    public int hashCode() {
        return Objects.hash(y, x);
    }
}