[백준] 2239 스도쿠

1. 문제

www.acmicpc.net/problem/2239

2239번: 스도쿠

2. 접근방법

스도쿠의 빈칸을 채우는 문제

 

가능한 모든 숫자에 대해서 넣어보고 넘어가고

넣어보고 넘어가고 반복하다 가능한 숫자가 없는 위치가 나오면 다시 돌아와서

가능한 다른 숫자를 넣고 다시 넘어가고

 

이런식으로 백트래킹을 통해 모든 0을 채워 넣으면 되는 문제이다.

 

 

 

3. 자바 코드

package algo;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class BOJ2239 {
	static int map[][];
	
	public static void main(String[] args) throws Exception {
		map = new int[9][9];
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for(int i = 0 ; i < 9 ; i++) {
			String s = br.readLine();
			for(int j = 0 ; j < 9 ; j++) {
				map[i][j] = Integer.parseInt(s.charAt(j)+"");
			}
		}
		
		go();
		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 go() { //백트
		Point myPoint = findzero();
		if(myPoint == null) {
			return true;
		}
		List<Integer> mycanlist = whatcan(myPoint.x,myPoint.y);
		
		if(mycanlist.size() == 0) {
			return false;
		}
		for(int i : mycanlist) {
			map[myPoint.x][myPoint.y] = i;
			if(go())
				return true;
		}
		map[myPoint.x][myPoint.y] = 0;
		return false;
	}
	
	static Point findzero() {
		for(int i = 0 ; i < 9; i++) {
			for(int j = 0 ; j < 9 ; j++) {
				if(map[i][j] == 0)
					return new Point(i,j);
			}
		}
		return null;
	}
	
	static List<Integer> whatcan(int x ,  int y){ //현재 위치 가능한 숫자 찾기
		List<Integer> can = new ArrayList<Integer>();
		boolean [] ten = new boolean[10];
		
		for(int i = 0 ; i < 9 ; i++) {
			ten[map[x][i]] = true;
			ten[map[i][y]] = true;
		}
		int startx = x - x%3;
		int starty = y - y%3;
		for(int i = startx ; i <startx+3; i++) {
			for(int j = starty ; j < starty+3 ; j++) {
				ten[map[i][j]] = true;
			}
		}
		for(int i = 1 ; i < 10 ; i++) {
			if(!ten[i])
				can.add(i);
		}
		return can;
	}
	
	

}

4. 마치며

원래 스도쿠를 가끔 풀곤해서 재밌게 풀었다.