[백준] 2580번 - 스도쿠 [Java]

https://www.acmicpc.net/problem/2580

 

[백준] 2580번 - 스도쿠 [Java]

[백준] 2580번 - 스도쿠 [Java]

[백준] 2580번 - 스도쿠 [Java]

---

1.  아이디어

 

재귀와 백트래킹을 통해 해결할 수 있는 문제로 DFS 알고리즘과 중복 순열 두 가지 방법으로 해결했다.

---

2. 문제풀이

 

DFS는 0행 0열부터 8행 8열까지 행 우선 순회하며 0이 아니면 다음 재귀로 넘어가고 0이면 1부터 9까지 넣어보고 다음 재귀로 넘어가도록 구현했다. 재귀 과정에서 1부터 9까지 전부 넣을 수 없으면 이전 재귀에서 잘못된 숫자가 들어갔던 것이므로 이전 재귀로 돌아가면 이전 재귀의 숫자를 안넣었던 것으로 처리하는 방식으로 구현했다. 행과 열, 정사각형에 대한 방문 체크로 숫자를 넣을 수 있는지 이때 방문 체크 배열은 3차원으로 만들어서 각 위치에 들어갈 수 없는 숫자를 등장 횟수로 구분했다. 단순히 boolean 타입으로 했을 때 방문 취소 시 엉뚱한 위치에서 방문 취소가 되는 에러가 있어서 개수로 카운팅하는 방식으로 구현했다.

중복 순열은 0이 등장한 위치들을 저장한 후 각 위치에 1부터 9까지 넣을 수 있으면 넣고 다음 재귀로 넘어가는 방식으로 구현했다. 원본 맵에 바로 숫자를 넣는 방식으로 구현해서 방문 체크는 숫자 넣기, 방문 취소는 0 넣기로 구현할 수 있었다.

두 가지 방식 모두 하나의 조합만 찾으면 더 반복할 필요가 없으므로 flag 변수로 완성된 조합이 있으면 계속 return 하도록 구현했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static final StringBuilder sb = new StringBuilder();

    private static final int[][] map = new int[9][9];
    private static final int[][][] visited = new int[9][9][1 + 9];
    private static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < 9; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (map[i][j] == 0) continue;

                for (int k = 0; k < 9; k++) {
                    // 같은 행 방문체크
                    visited[k][j][map[i][j]]++;

                    // 같은 열 방문체크
                    visited[i][k][map[i][j]]++;

                    // 같은 정사각형 방문체크
                    visited[i / 3 * 3 + k / 3][j / 3 * 3 + k % 3][map[i][j]]++;
                }
            }
        }

        dfs(0, 0);

        bw.write(sb.toString());
        bw.flush();
    }

    private static void dfs(int r, int c) {
        // 한번만 발견하면 계속 재귀 종료
        if (flag) return;

        // 종료 조건
        if (r == 9) {
            flag = true;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(map[i][j]).append(" ");
                }
                sb.append("\n");
            }
            return;
        }

        // 0이 아닌 칸은 넘어감
        if (map[r][c] != 0) {
            if (c == 8) dfs(r + 1, 0);
            else dfs(r, c + 1);
            return;
        }

        // 0인 칸은 방문해보고 아니면 방문 취소
        for (int i = 1; i <= 9; i++) {
            if (visited[r][c][i] > 0) continue;

            map[r][c] = i;
            for (int k = 0; k < 9; k++) {
                visited[k][c][map[r][c]]++;
                visited[r][k][map[r][c]]++;
                visited[r / 3 * 3 + k / 3][c / 3 * 3 + k % 3][map[r][c]]++;
            }

            if (c == 8) dfs(r + 1, 0);
            else dfs(r, c + 1);

            for (int k = 0; k < 9; k++) {
                visited[k][c][map[r][c]]--;
                visited[r][k][map[r][c]]--;
                visited[r / 3 * 3 + k / 3][c / 3 * 3 + k % 3][map[r][c]]--;
            }
            map[r][c] = 0;
        }
    }

}

import java.io.*;
import java.util.*;

public class Main {

    private static final StringBuilder sb = new StringBuilder();

    private static final List<int[]> list = new ArrayList<>();

    private static final int[][] map = new int[9][9];
    private static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < 9; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (map[i][j] == 0) list.add(new int[]{i, j});
            }
        }

        permutation(0);

        bw.write(sb.toString());
        bw.flush();
    }

    // 0인 칸들에 대해 1 ~ 9를 배치하는 중복 순열
    private static void permutation(int selIdx) {
        if (flag) return;

        if (selIdx == list.size()) {
            flag = true;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(map[i][j]).append(" ");
                }
                sb.append("\n");
            }
            return;
        }

        for (int n = 1; n <= 9; n++) {
            if (!canPlace(list.get(selIdx)[0], list.get(selIdx)[1], n)) continue;

            map[list.get(selIdx)[0]][list.get(selIdx)[1]] = n;
            permutation(selIdx + 1);
            map[list.get(selIdx)[0]][list.get(selIdx)[1]] = 0;
        }
    }

    // 스도쿠에서 배치 가능한 숫자인지 boolean 타입으로 반환
    private static boolean canPlace(int r, int c, int num) {
        boolean canPlace = true;

        for (int k = 0; k < 9; k++) {
            if (map[k][c] == num || map[r][k] == num || map[r / 3 * 3 + k / 3][c / 3 * 3 + k % 3] == num) {
                canPlace = false;
                break;
            }
        }

        return canPlace;
    }

}

---

4. 후기

 

- DFS

- 중복 순열