[백준]JAVA - 2239번: 스도쿠

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

2239번: 스도쿠

풀이

어린 시절에 많이 풀었던 스도쿠가 보이길래 한 번 풀어봤다.

문제의 조건은 우리가 알고 있는 스도쿠와 동일하다.

 

1. 각 행과 열에 중복되지않은 9개의 숫자(1-9)가 존재해야 한다. 
2. 3x3 크기의 박스에 중복되지않은 9개의 숫자(1-9)가 존재해야 한다. 

스도쿠에서는 위 두 가지 조건만 신경써주면서 빈칸에 1-9를 넣어주는 dfs를 돌려주면 된다.

하지만 dfs만 계속 돌리면 시간 초과가 발생하기 때문에 백트래킹을 해야한다.

 

우선 숫자를 입력해야 하는 위치를 zero라는 pos 객체 ArrayList에 저장해 준다.

for (int i=0; i<9; i++) {
    String str = br.readLine();
    for (int j=0; j<9; j++) {
        map[i][j] = str.charAt(j) - '0';
				
        if (map[i][j] == 0) {
            zero.add(new Pos(i, j));
        }
    }
}

이후에 dfs를 돌려주면 된다.

dfs의 종료 조건은 0부터 시작한 level 변수가 입력해야 하는 칸의 개수와 동일해졌을 때이다.

즉, 모든 숫자가 입력되었을 때 종료한다.

 

public static void dfs(int level) {
    if (level == zero.size()) {
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
        System.exit(0);
    }
		
    Pos now = zero.get(level);
    for (int i=1; i<10; i++) {
        // 백트래킹
        if (map[now.x][now.y] == 0 && checkBox(now.x, now.y, i) && checkRow(now.x, now.y, i)) {
            map[now.x][now.y] = i;
            dfs(level+1);
            map[now.x][now.y] = 0;
        }
    }
}

1-9의 숫자를 하나씩 넣어주면서 스도쿠의 조건에 맞으면 해당 숫자로 변경시켜 주고 dfs(level+1)을 태운다. 이후에 숫자가 잘 못 들어갔다고 판단되면 숫자를 다시 0으로 만들어주면 된다.

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int[][] map;
    static ArrayList<Pos> zero = new ArrayList<>();
	
    public static class Pos {
        int x;
        int y;
		
        public Pos (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        map = new int[9][9];
        for (int i=0; i<9; i++) {
            String str = br.readLine();
            for (int j=0; j<9; j++) {
                map[i][j] = str.charAt(j) - '0';
				
                if (map[i][j] == 0) {
                    zero.add(new Pos(i, j));
                }
            }
        }
		
        dfs(0);
    }
	
    public static void dfs(int level) {
        if (level == zero.size()) {
            for (int i=0; i<9; i++) {
                for (int j=0; j<9; j++) {
                    System.out.print(map[i][j]);
                }
                System.out.println();
            }
            System.exit(0);
        }
		
        Pos now = zero.get(level);
        for (int i=1; i<10; i++) {
            
            // 스도쿠 조건에 해당하는 경우
            if (map[now.x][now.y] == 0 && checkBox(now.x, now.y, i) && checkRow(now.x, now.y, i)) {
                map[now.x][now.y] = i;
                dfs(level+1);
                map[now.x][now.y] = 0;
            }
        }
    }
	
    // BOX 체크 - 동일한 숫자 존재 여부 판단
	public static boolean checkBox(int x, int y, int num) {
        int sX = (x/3)*3;
        int sY = (y/3)*3;
		
        for (int i=sX; i<sX+3; i++) {
            for (int j=sY; j<sY+3; j++) {
                if (map[i][j] == num) {
                    return false;
                }
            }
        }
		
        return true;
    }
	
    // 한 줄 체크 - 동일한 숫자 존재 여부 판단
    public static boolean checkRow(int x, int y, int num) {
        for (int i=0; i<9; i++) {
            if (map[i][y] == num) {
                return false;
            }
			
            if (map[x][i] == num) {
                return false;
            }
        }
		
        return true;
    }
}