백준 2580. 스도쿠 :: 돼지개발자

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

"백트래킹"

아... 분명 시간 초과가 날 것이 없다고 생각했는데, 또 소스를 봐도 날것이 없다고 생각했는데...

전체적인 로직은 잘 짰으나 아래와 같은 실수를 했다. DFS 탐색에 BFS 처럼 가능한 list를 다 순회하다니. 

for (int i = idx; i < size; i++) {
    Node node = list.get(i);
    
    for (int j = 1; j < 10; j++) {
        // 불가능한 경우
        if(!possible(node.x,node.y,j)) 
            continue;
        
        map[node.x][node.y] = j;
        solve(i+1,cnt+1);
        if(ok) return ;
        map[node.x][node.y] = 0;
    }
}

한가지 더 유의할 점은

"스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다"

라고 했으니, ok boolean 플래그를 두어 최초 발견 이후 탐색을 하지 않도록 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
class Main {
    
    static int[][] map = new int[9][9];
    static ArrayList<Node> list = new ArrayList<>();
    static int size;
    static boolean ok ;
    static StringBuilder sb = new StringBuilder();
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for (int i = 0; i < 9; i++) {
            StringTokenizer 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 Node(i, j));
            }
        }
        size = list.size();
        
        solve(0,0);
        
        System.out.println(sb.toString());
    }
    
    static void solve(int idx, int cnt) {
        if(ok) return;
        
        if(cnt == size) {
            ok = true;
            
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(map[i][j]+" ");
                }
                sb.append("\n");
            }
            
            return ;
        }
        
        Node node = list.get(idx);
        
        for (int j = 1; j < 10; j++) {
            // 불가능한 경우
            if(!possible(node.x,node.y,j)) 
                continue;
            
            map[node.x][node.y] = j;
            solve(idx+1,cnt+1);
            if(ok) return ;
            map[node.x][node.y] = 0;
        }
    }
    
    static boolean possible(int x, int y, int v) {
        // 가로, 세로
        for (int i = 0; i < 9; i++) {
            if(map[i][y] == v || map[x][i] == v) {
                return false;
            }
        }
        // 3x3 격자 내부
        for (int i = (x/3)*3; i < (x/3)*3 + 3; i++) {
            for (int j = (y/3)*3; j < (y/3)*3 +3; j++) {
                if(map[i][j] == v) {
                    return false;
                }
            }
        }
        return true;
    }
}
 
class Node {
    int x;
    int y;
    
    Node (int x , int y ) {
        this.x = x;
        this.y = y;
    }
}