[백준] 2580 스도쿠 (Java/자바)

 

문제

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

 

 

문제풀이

백트래킹 문제로 아래와 같은 흐름을 따른다.

 

1. 현재 위치에서 가능한 번호를 넣은 채 다음으로 넘어간다.

2. 순서대로 map 전체를 탐방하며 가능한 번호로 계속 넘어간다.

3. 만약, 중간에 가능한 번호가 없는 구역이 나타나면 이전으로 넘어가서 가능한 번호를 다시 탐색한다.

4. 1~3번을 반복하며 map의 끝까지 갔을 경우 종료한다.

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int[][] map = new int[9][9];
	
    public static void main(String[] args) throws Exception {
    	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());
    		}
    	}
    	
    	solve(0, 0);
    	
    	br.close();
    }
    
    public static void solve(int y, int x) {
    	// x축의 끝
    	if(x == 9) {
    		solve(y+1, 0);
    		return;
    	}
    	
        // 종점 까지 도달한 상황
        // 이때가 종료 시점이 된다.
    	if(y == 9) {
    		print();
    		System.exit(0);
    	}
    	
    	if(map[y][x] == 0) {
    		for(int i = 1; i <= 9; i++) {
        		if(!valid(y, x, i)) continue;
        		map[y][x] = i;
        		solve(y, x+1);
        	}
            // Back-Tracking 가능하도록 0으로 셋팅해준다.
    		map[y][x] = 0;
    		return;
    	}
    	
    	solve(y, x+1);
    }
    
    public static boolean valid(int y, int x, int k) {
    	// 가로, 세로
    	for(int i = 0; i < 9; i++) {
    		if(map[y][i] == k) return false;
    		if(map[i][x] == k) return false;
    	}
    	
    	for(int i = (y/3)*3; i < (y/3+1)*3; i++) {
    		for(int j = (x/3)*3; j < (x/3+1)*3; j++) {
    			if(map[i][j] == k) return false;
    		}
    	}
    	
    	return true;
    }
    
    public static void print() {    	
    	for(int i = 0; i < 9; i++) {
    		for(int j = 0; j < 9; j++) {
    			System.out.printf("%d ", map[i][j]);
    		}
    		System.out.println();
    	}
    }
}