[알고리즘] 백준 > #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);
}
}
Author And Source
이 문제에 관하여([알고리즘] 백준 > #2580. 스도쿠), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cchloe2311/알고리즘-백준-2580.-스도쿠저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)