[BOJ 2239] 스도쿠 (Java)

BOJ 2239 스도쿠

난이도 : 골드 4

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

2239번: 스도쿠

 

전략

간단한 백트래킹 문제로 예전에 c++로 한번 풀었던 적이 있다. (BOJ 2580)

재귀에 너무 익숙해져있는 것 같아서 이번에는 스택으로 구현해보고자 풀어보았다.

 

시행착오

재귀로는 정적 배열을 수정하면서 간단하게 백트래킹을 구현할 수 있었다.

스택으로 하려니까 실패했을 때 이전 상태로 돌리는 것을 어떻게 처리할지 고민을 많이 했다.

따라서 clear 메소드를 만들어서 현재 위치보다 뒤에 있는 빈칸을 0으로 직접 만들어주었다..

스택 구현의 로직 상 한 번 0이 나오면 그 이후에는 아직 탐색 중이지 않은 빈칸이므로 효율을 위해서 0이 나오기 전까지만 clear를 했다.

 

코드

import java.util.*;

public class Main {

    static int map[][];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        map = new int[9][9];
        ArrayList<Position> blanks = new ArrayList<>();
        Stack<Position> stack = new Stack<>();

        for (int i=0; i<9; i++) {
            String line = sc.nextLine();
            for (int j=0; j<9; j++) {
                int num = line.charAt(j) - '0';
                map[i][j] = num;
                if (num == 0) {
                    Position pos = new Position(i, j, 0);
                    pos.cnt = blanks.size();
                    blanks.add(pos);
                }
            }
        }

        Position first = new Position(blanks.get(0).y, blanks.get(0).x, 0);
        first.cnt = -1;
        stack.push(first);

        while (!stack.isEmpty()) {
            Position cur = stack.pop();
            map[cur.y][cur.x] = cur.num;

            if (cur.cnt == blanks.size() - 1)
                break;

            clear(blanks, cur.cnt + 1);
            Position seek = blanks.get(cur.cnt + 1);

            for (int t=9; t>=1; t--) {
                seek.num = t;
                if (checkRow(seek) && checkCol(seek) && checkBox(seek)) {
                    Position next = new Position(seek.y, seek.x, t);
                    next.cnt = seek.cnt;
                    stack.push(next);
                }
            }
        }

        printSolution();
    }

    static void clear(ArrayList<Position> blanks, int idx) {
        for (int i=idx; i<blanks.size(); i++) {
            Position pos = blanks.get(i);
            if (map[pos.y][pos.x] == 0)
                break;
            map[pos.y][pos.x] = 0;
        }
    }

    static void printSolution() {
        for (int i=0; i<9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    static boolean checkRow(Position pos) {
        for (int i=0; i<9; i++)
            if (map[pos.y][i] == pos.num)
                return false;
        return true;
    }

    static boolean checkCol(Position pos) {
        for (int i=0; i<9; i++)
            if (map[i][pos.x] == pos.num)
                return false;
        return true;
    }

    static boolean checkBox(Position pos) {
        int sx, sy;
        sx = pos.x / 3 * 3;
        sy = pos.y / 3 * 3;
        for (int i=sy; i<sy+3; i++)
            for (int j=sx; j<sx+3; j++)
                if (map[i][j] == pos.num)
                    return false;
        return true;
    }

    static class Position {
        int y;
        int x;
        int num;

        int cnt = 0;

        Position(int y, int x, int num) {
            this.y = y;
            this.x = x;
            this.num = num;
        }
    }
}

 

깨달은 점

스택 사용한 탐색 연습도 좀 해놔야겠다. 코드도 더 깔끔하게 고칠 수 있을 것 같다.