문제 : boj2239
row기준 9개, 세로기준 9개, 3x3으로 나뉜 9개에 모두 1~9가 하나씩 들어가기만 하면 된다.
따라서 로직은 다음과 같다.
1. 입력에서 0이 아닌 칸에 대해 위 3개의 조건을 체크한다.
2. 0인 칸 모두에 대해 차례대로 1~9중 들어갈 수 있는 숫자를 무작정 넣어본다.
3. 그렇게 해서 0인칸 모두를 채울 수 있는 경우가 나온다면 그대로 출력하면 된다. 그렇지 않다면 바로 직전 단계로 돌아가서 다른 수를 넣어본다.(따라서 백트래킹 문제이다.)
다음 스도쿠 이미지를 보자.
저 빨간부분에는 우선 row를 기준으로 보면(초록색 선) 아직 체크안된 값은 1과 4이다. 그리고 col기준(파란선)으로 보면 역시 1과 4가 들어갈 수 있다. 격자 기준(연두색)으로 보면 1,4,9가 아직 안나왔다. 따라서 셋 다 만족하는건 1과 4 이므로 우선 4를 넣어본다.
다음껄 보자. row기준으론 1만 가능하고, col기준으로는 4만 가능하다. 격자 기준으로는 4와 3이 가능하다. 따라서 셋 다 만족하는 경우는 없으며, 이 스도쿠는 더이상 진행할 수 없다. 따라서 이전으로 되돌아간다.
다시 이전으로 되돌아왔다. 이번엔 1을 넣는다. 그럼 그 다음 칸은 4를 넣어 진행할 수 있다. 이런식으로 해당 칸에서 가능한 값들을 넣어보면서 모든 빈칸을 채울 수 있는 경우가 나올 때 까지 전부 넣어보면 된다.
사실 로직상으론 단순한 백트래킹 문제이긴한데, 3개의 경우를 모두 체크해야 하므로 다소 구현이 어려울 수 있는 문제이다. 이 때 1~9가 등장했는지 체크할 수 있는 방법은 여러가지가 있겠는데, 배열로 해도 되고 HashSet으로 해도 된다. 좀 더 시간을 줄여서 해보려면 이하 제가 짠 코드처럼 bit 연산을 사용하면 된다. 참고로 HashSet으로 한게 700ms, bit연산을 이용한게 192ms 정도 나왔다. 메모리 또한 bit 연산을 이용한 체크방식이 10배이상 작게든다.
그리고 '답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다.'에 대한 처리는 간단히 더 낮은 수 부터 대입하며 백트래킹을 진행하면 얻을 수 있다. 예를들어 코드의 56 line에서 처럼 1부터 9까지 대입하며, 문제의 답이 나오는 순간 재귀 호출을 종료하며 답을 출력한다. 이와 같은 방식으로 사전식으로 앞서는 것을 출력할 수 있다.
코드 : github
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
class Candidate {
int r,c,gridNum;
public Candidate(int r, int c, int gridNum) {
this.r = r;
this.c = c;
this.gridNum = gridNum;
}
}
public class Main {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private int[][] chk = new int[3][9];
private int[][] answer = new int[9][9];
private ArrayList<Candidate> candidate = new ArrayList<>();
private void initUserInput() throws Exception {
for (int i = 0; i < 9; i++) {
String line = br.readLine();
for (int j = 0; j < 9; j++) {
int cur = line.charAt(j)-'0';
int gridNum = i/3*3+j/3;
if (cur == 0) {
candidate.add(new Candidate(i,j,gridNum));
continue;
}
answer[i][j] = cur;
chk[0][i]|=1<<cur;
chk[1][j]|=1<<cur;
chk[2][gridNum]|=1<<cur;
}
}
}
private void printAnswer() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(answer[i][j]);
}
sb.append('\n');
}
System.out.print(sb);
}
private boolean search(int idx) {
if (idx == candidate.size()) {
return true;
}
Candidate cur = candidate.get(idx);
for (int num = 1; num <= 9; num++) {
if ( (chk[0][cur.r]&1<<num)!=0 || (chk[1][cur.c]&1<<num)!=0 || (chk[2][cur.gridNum]&1<<num)!=0 )
continue;
chk[0][cur.r]|=1<<num;
chk[1][cur.c]|=1<<num;
chk[2][cur.gridNum]|=1<<num;
answer[cur.r][cur.c] = num;
if (search(idx+1)) return true;
chk[0][cur.r]&=~(1<<num);
chk[1][cur.c]&=~(1<<num);
chk[2][cur.gridNum]&=~(1<<num);
}
return false;
}
private void solution() throws Exception {
initUserInput();
search(0);
printAnswer();
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}
'PS > BOJ' 카테고리의 다른 글
백준 15922 자바 - 아우으 우아으이야!! (BOJ 15922 JAVA) (0) | 2022.01.28 |
---|---|
백준 1817 자바 - 짐 챙기는 숌 (BOJ 1817 JAVA) (0) | 2022.01.27 |
백준 2580 자바 - 스도쿠 (BOJ 2580 JAVA) (0) | 2022.01.26 |
백준 14467 자바 - 소가 길을 건너간 이유 1 (BOJ 14467 JAVA) (0) | 2022.01.25 |
백준 20040 자바 - 사이클 게임 (BOJ 20040 JAVA) (0) | 2022.01.24 |
댓글