백준 2239번 스도쿠 (JAVA)

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

2239번: 스도쿠

 

저는 해당 문제를 DFS를 활용해 해결하였습니다.

DFS를 이용해 0인 곳에서 사용할 수 있는 값들을 확인하고 (prunning) 이 값들을 넣어보면서 진행하였습니다.

처음에 다시 0 으로 되돌리는 코드가 없어서 계속 제대로 된 값이 되지 않았습니다.

DFS라면 백트래킹을 하기 때문에 원본으로 되돌리는 코드가 있어야합니다.

그리고 0인 곳에 1 ~ 9까지 값을 대입하고 해당 값이 유효한 지를 확인하도록 코드를 작성하였는데, 이렇게 하게되면 시간 초과는 나지 않지만 비효율적입니다. 

(1~9대입하고 유효한지를 확인하기 때문에 한 곳에서 9번 유효검사합니다.)

1~9까지 대입하지 않고 유효한 값들을 추출하면 1~9까지 대입하지 않기 때문에 이전방법보다 효율적이게 됩니다.

(한곳에서 한번의 확인으로 1~9에 유효한 값을 알 수 있다.)

 

package BOJ.Simulation;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.function.Function;

public class BOJ_2239_2 {

    private static int SIZE = 9;

    private static boolean fillMap(int y, int x, int[][] map) {
        if (y >= SIZE) {
            return true;
        }
        int ny = y;
        int nx = x;
        nx++;
        if (nx >= SIZE) {
            nx = 0;
            ny++;
        }
        if (map[y][x] == 0) {
            boolean[] used = checkValid(y, x, map);
            for (int i = 1; i <= SIZE; i++) {
                if (used[i]) {
                    continue;
                }
                map[y][x] = i;
                if (fillMap(ny, nx, map)) {
                    return true;
                }
            }
            map[y][x] = 0;
            return false;
        } else {
            return fillMap(ny, nx, map);
        }
    }

    private static boolean[] checkValid(int y, int x, int[][] map) {
        boolean[] used = new boolean[SIZE + 1];
        for(int i = 0 ; i < SIZE ; i++){
            used[map[y][i]] = true;
            used[map[i][x]] = true;
        }
        int ny = y / 3;
        int nx = x / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int num = map[3 * ny + i][3 * nx + j];
                used[num] = true;
            }
        }
        return used;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String, Integer> stoi = Integer::parseInt;
        int[][] map = new int[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) {
            String command = br.readLine();
            for (int j = 0; j < SIZE; j++) {
                map[i][j] = stoi.apply(command.charAt(j) + "");
            }
        }
        fillMap(0, 0, map);
        print(map);
    }

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