백준 2239 스도쿠 [자바]

in Develop / Solving

baekjoon 2239 스도쿠

java

문제 분석

  • 스도쿠 판이 주어진다.
  • 빈칸을 잘 채워 봐라.

입력조건

9*9에 걸쳐서 숫자가 입력됨(각 줄에 빈칸 없이 입력)

풀이과정

  • dfs + 백트래킹 + 비트마스킹
  • 행, 열, 3*3 판의 세 개의 비트 배열을 관리하고,
    내가 숫자를 넣을 때 마다 해당하는 비트에 겹치는 수가 있는지 판단, 이를 통해 넣을 수 있는지 없는지를 판단한다.
  • 한 번 답을 찾으면, dfs로 들어간 깊이에서, 아무것도 건드리지 않고 스택을 전부 비워버려야 한다.
    이를 위해서 재귀함수를 boolean 형태로 리턴하도록 했고, 모든 위치를 확인하고 끝나면(스도쿠를 다 채우면) true를 리턴, 하나라도 채우는 것이 불가능하면 false를 리턴하도록 하였다.
  • 재귀함수에서 다시 이 boolean을 받을 때
    • true를 리턴받았으면 그대로 지금 함수도 리턴헤배린다.
      이렇게 되면 모든 재귀함수가 리턴되어서, 재귀를 종료하게 된다.
    • false를 리턴받았으면 현재 위치에 넣었던 숫자를 빼고(비트에 넣었던 것도 다 뺀다.)
      다음 숫자를 테스트 해 본다.
  • 답을 만들 수 없는 경우가 주어지지 않기에, 위처럼 문제를 해결할 수 있었다.ㅌ

코드 구성

  • 입력 받기

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int i = 0; i < 9; i++) {
    String line = br.readLine();
    for(int j = 0; j < 9; j++) {
        map[i][j] = line.charAt(j) - '0';
  
        if(map[i][j] != 0) {
            colbit[j] = colbit[j] | 1<<map[i][j];
            rowbit[i] = rowbit[i] | 1<<map[i][j];
            mapbit[getidx(i, j)] = mapbit[getidx(i, j)] | 1<<map[i][j];
        }
    }
}
    • rowbit, colbit, mapbit는 각각 행을 합친 비트, 열을 합친 비트 3*3을 합친 비트이다.
    • getidx는 i, j를 가지고 3*3의 어느 위치인지를 알려주는 함수이다.

  • 재귀호출

    public static boolean solve(int rc) {		
    // 넣을 위치 찾기
    while ( rc < 81 && map[rc/9][rc%9] != 0) rc++;
    if(rc >= 81) return true;
  
    int r = rc/9;
    int c = rc%9;
  
    for(int i = 1; i <= 9; i++) {
        // 넣을 수 없는 상황이면 다음걸로
        if(		(rowbit[r] & 1<<i) > 0 ||
           (colbit[c] & 1<<i) > 0 ||
           (mapbit[getidx(r, c)] & 1<<i) > 0)
            continue;
  
        // 넣기
        map[r][c] = i;
        rowbit[r] = rowbit[r] | 1<<i;
        colbit[c] = colbit[c] | 1<<i;
        mapbit[getidx(r, c)] = mapbit[getidx(r, c)] | 1<<i;
        // 만약 지금 했던걸로 결과가 나오면, 여기서 맨 처음까지 리턴해버림.
        if( solve(rc+1) ) return true;
  
        // 통과 못했으면, 원위치
        map[r][c] = 0;
        rowbit[r] = rowbit[r] ^ 1<<i;
        colbit[c] = colbit[c] ^ 1<<i;
        mapbit[getidx(r, c)] = mapbit[getidx(r, c)] ^ 1<<i;
    }
    // 아무것도 못넣으면 불가능
    return false;
}

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BJ2239_스도쿠 {
	public static int[][] map = new int[9][9];
	public static int[] rowbit = new int[9];
	public static int[] colbit = new int[9];
	public static int[] mapbit = new int[9];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for(int i = 0; i < 9; i++) {
			String line = br.readLine();
			for(int j = 0; j < 9; j++) {
				map[i][j] = line.charAt(j) - '0';
				
				if(map[i][j] != 0) {
					colbit[j] = colbit[j] | 1<<map[i][j];
					rowbit[i] = rowbit[i] | 1<<map[i][j];
					mapbit[getidx(i, j)] = mapbit[getidx(i, j)] | 1<<map[i][j];
				}
			}
		}
		// 입력 완료
		
		solve(0);
		for(int i = 0; i < 9; i++) {
			for(int j = 0; j < 9; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
	public static boolean solve(int rc) {		
		// 넣을 위치 찾기
		while ( rc < 81 && map[rc/9][rc%9] != 0) rc++;
		if(rc >= 81) return true;
		
		int r = rc/9;
		int c = rc%9;
		
		for(int i = 1; i <= 9; i++) {
			// 넣을 수 없는 상황이면 다음걸로
			if(		(rowbit[r] & 1<<i) > 0 ||
					(colbit[c] & 1<<i) > 0 ||
					(mapbit[getidx(r, c)] & 1<<i) > 0)
				continue;
			
			// 넣기
			map[r][c] = i;
			rowbit[r] = rowbit[r] | 1<<i;
			colbit[c] = colbit[c] | 1<<i;
			mapbit[getidx(r, c)] = mapbit[getidx(r, c)] | 1<<i;
			// 만약 지금 했던걸로 결과가 나오면, 여기서 맨 처음까지 리턴해버림.
			if( solve(rc+1) ) return true;
			
			// 통과 못했으면, 원위치
			map[r][c] = 0;
			rowbit[r] = rowbit[r] ^ 1<<i;
			colbit[c] = colbit[c] ^ 1<<i;
			mapbit[getidx(r, c)] = mapbit[getidx(r, c)] ^ 1<<i;
		}
		// 아무것도 못넣으면 불가능
		return false;
	}
	
	// mapbit의 인덱스를 반환해주는 함수
	private static int getidx(int i, int j) {
		return (i/3)*3 + j/3;
	}
}