[Java] 백준 2239번 : 스도쿠

1. 문제

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

2239번: 스도쿠

 

 

 

2. 풀이과정

작은 수부터 순열 생성하면서 simulation한다.

 

[simulation 단계]

1. 해당 칸에 번호 i를 놓을 수 있는지 확인 => 못 놓으면 다음 i보고, 놓을 수 있으면 다음 단계로

2. 해당 칸에 번호를 놓고, 방문 체크

3. 다음 칸을 보자

4. 다음 칸들을 다 본 후엔, 2번 과정을 복구

 

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

public class Boj2239 {
	static int map[][], size;
	static ArrayList<int[]> blanks;
	static int rVisited[] = new int[9];//행방문체크
	static int cVisited[] = new int[9];//열방문체크
	static int sVisited[] = new int[9];//3x3구역 방문체크
	
	public static boolean go(int[][] m, int cnt) {
		if(cnt==size) {//작은 값부터 순열을 놓기 때문에, 처음 다 채우는 순간이 최소 => 바로 반환
			for(int i=0;i<9;i++) {
				for(int j=0;j<9;j++) {
					System.out.print(m[i][j]);
				}
				System.out.println();
			}
			return true;//void가 아닌 true로 반환해서 true면 더이상 진행안하도록 하자
		}
		
		//1~9 들어갈 수 있으면 넣어보자
		for(int i=1; i<=9; i++) {
			int x = blanks.get(cnt)[0];
			int y = blanks.get(cnt)[1];
			if(!isAvailable(x, y, i)) {
				continue;
			}
			m[x][y] = i;
			//방문체크
			rVisited[x] |= (1<<i);
			cVisited[y] |= (1<<i);
			sVisited[x/3*3+y/3] |= (1<<i);
			
			//재귀
			if(go(m, cnt+1)) return true; //true면 끝내자
			
			//복구
			m[x][y] = 0;
			rVisited[x] &= ~(1<<i);//i번째만 0으로 설정!
			cVisited[y] &= ~(1<<i);
			sVisited[x/3*3+y/3] &= ~(1<<i);
		}	
		return false;
	}
	
	//가로, 세로, 3x3구역에 같은 값이 없으면 true 반환
	public static boolean isAvailable(int x, int y, int n) {
		if((rVisited[x] & (1<<n)) != 0) return false;
		if((cVisited[y] & (1<<n)) != 0) return false;
		if((sVisited[x/3*3+y/3] & (1<<n)) !=0) return false;
		return true;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new int[9][9];
		blanks = new ArrayList<>();
		//입력
		for(int i=0;i<9;i++) {
			String s = br.readLine();
			for(int j=0;j<9;j++) {
				map[i][j] = s.charAt(j)-'0';
				if(map[i][j]==0) {//0인 값 = 빈칸에 추가
					blanks.add(new int[] {i, j});
				}
				else {//0이 아닌 값 = 행, 열, 구역  => 번호 사용했음을 체크
					rVisited[i] |= (1<<map[i][j]);
					cVisited[j] |= (1<<map[i][j]);
					sVisited[i/3*3+j/3] |= (1<<map[i][j]);
				}
			}
		}
		size = blanks.size();//빈칸 개수
		go(map, 0);//실행
	}
}