백준 2580 자바 - 스도쿠 (BOJ 2580 JAVA)

문제 : boj2580

 

 

  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배이상 작게든다.

 

 

 

코드 : 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*2)-'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]).append(' ');
            }
            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();
    }
}