[java]스도쿠 - 백준2239

문제

• 스도쿠(백준2239)

풀이

문제 해석을 하자면,

• 문제에서 주어진 입력을 가지고 스도쿠 퍼즐을 만들어 출력해야 한다.
• 숫자가 채워지지 않은 칸은 0으로 입력이 주어지므로 이부분을 수정하여 스도쿠 퍼즐을 만들어야 한다.

풀이

• 따로 필요한 알고리즘은 없고 “구현” 문제이다. -> 재귀, 백트래킹 알고리즘만 알면 풀 수 있다.
• 재귀(dfs) 는 어떻게??
  • 깊이는 입력으로 주어지는 0 의 개수로 설정한다. -> 기저 조건으로 활용
  • 너비(재귀 가지치기)의 경우는 1~9 가 가능하다. -> 재귀 조건으로 활용
• 제일 중요한 스도쿠 검증은??
  • check() 함수 구현 -> 가로, 세로, 3x3 다 확인해서 해당 자리에 삽입 가능한 숫자인지 판단 함수
  • visited[] 사용하여 검증하자. -> 삽입할 숫자는 map(=outArr) 에 삽입하고 재귀하자 + “백트래킹까지”
    • 1~9 중 삽입 가능한 숫자로 재귀 가지치기 하는것
    • 백트래킹은 재귀하면서 수정된 outArr 값을 0 으로 수정함으로써 원본으로 되돌린다.
• 출력은 사전식을 어떻게 지키나??
  • 입력으로 주어진 0의 좌표를 “왼쪽 위에서” 부터 순서대로 접근과
  • 1~9 순서로 재귀 접근하면 처음나오는 정답 값이 사전순서 1등이다.
  • 따라서 이때 System.exit(0); -> 강제종료

코드

static int M;
static String[] input = new String[10];
static int[][] outArr = new int[10][10];
static List<Pair> inArr = new ArrayList<>(); // M개 만큼 채워짐
static StringBuilder sb = new StringBuilder();

static void check(boolean[] visited, Pair cur, int depth) {
    //가로 체크
    for (int j = 1; j < 10; j++) {
        if (outArr[cur.x][j] != 0) {
            visited[outArr[cur.x][j]] = true;
        }
    }
    //세로 체크
    for (int i = 1; i < 10; i++) {
        if (outArr[i][cur.y] != 0) {
            visited[outArr[i][cur.y]] = true;
        }
    }
    //3x3 체크
    int stX = ((cur.x-1)/3)*3; // 인덱스 1부터 사용중이라 임시로 0으로 바꾸기 위해 -1
    int stY = ((cur.y-1)/3)*3;
    for (int i = stX + 1; i < (stX + 1) + 3; i++) {
        for (int j = stY + 1; j < (stY + 1) + 3; j++) {
            if (outArr[i][j] != 0) {
                visited[outArr[i][j]] = true;
            }
        }
    }
    //재귀
    for (int i = 1; i < 10; i++) {
        if(visited[i]) continue;
        outArr[cur.x][cur.y] = i;
        dfs(depth + 1);
        outArr[cur.x][cur.y] = 0; //backtracking
    }
}

static void dfs(int depth) {
    //base condition
    if (depth == M) {
        for (int i = 1; i < 10; i++) {
            for (int j = 1; j < 10; j++) {
                sb.append(outArr[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb);
        System.exit(0); //강제종료
        return;
    }
    //recursion
    boolean[] visited = new boolean[10]; // 매번 재생성
    Pair nxt = inArr.get(depth);
    check(visited, nxt, depth);
}

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    for (int i = 1; i < 10; i++) {
        input[i] = br.readLine();
        for (int j = 1; j < 10; j++) {
            outArr[i][j] = input[i].charAt(j-1)-'0';
            if (input[i].charAt(j-1) == '0') {
                inArr.add(new Pair(i, j)); // 좌표기록
                M++;
            }
        }
    }
    //run & output
    dfs(0);
}

static class Pair{
    int x; int y;

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

느낀점

생략