[문제] 백준 2580번 스도쿠

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

내풀이

 

체크해야 할 조건은 

1. 자기 위치에서의 행, 열에서 같은 숫자 있으면 안됨

2. 자기 위치에서의 부분 사각형에 같은 숫자 있으면 안됨

 

또, 계속 틀렸던 이유는 

재귀에서  스도쿠가 가능하지 않아서 되돌아올 때, 해당 숫자를 0으로 다시 초기화 해야한다는 것이다.

package Week5;

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

/*
 * 	BOJ # 2580 스도쿠 
 * */
public class BOJ_2580 {
	static int[][] map;
	static ArrayList<int[]> list; // 빈칸 리스트

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = 9;
		map = new int[N][N];
		list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 0) {
					list.add(new int[] { i, j });	//빈칸 모아두기
				}
			}
		}
		solve(0);
	}
	
	static void solve(int idx) {
		if(idx==list.size()) {	// 빈칸 다 채웠으면 종료
			StringBuilder sb = new StringBuilder();
			for(int i=0;i<9;i++) {
				for(int j=0;j<9;j++) {
					sb.append(map[i][j]).append(' ');
				}
				sb.append('\n');
			}
			System.out.print(sb);
			System.exit(0);
			return;
		}
		
		for(int i=1;i<=9;i++) {
			int[] curr = list.get(idx);	// 현재 빈칸
			map[curr[0]][curr[1]] = i;	// i번으로 채워보기
			if(check(curr[0], curr[1])) {	// 스도쿠가 가능하면
				solve(idx+1);				// 다음 빈칸으로 진행
			}
			map[curr[0]][curr[1]] = 0;	// **스도쿠 가능하지 않아 돌아왔을 때 0으로 되돌려 놓기**
		}
	}
	
	// (r,c)에 있는 숫자가 스도쿠가 가능한지 확인하는 함수
	static boolean check(int r, int c) {
		// 행 확인
		for(int i=0;i<9;i++) {
			if(i==r) continue;
			if(map[i][c] == map[r][c]) return false;
		}
		
		// 열 확인
		for(int i=0;i<9;i++) {
			if(i==c) continue;
			if(map[r][i] == map[r][c]) return false;
		}
		
		//사각형 내부 확인
		int startR = (r/3)*3;	// 해당 좌표가 포함된 3*3 사각형의 영역 구하기
		int startC = (c/3)*3;
		for(int i=startR;i<startR+3;i++) {
			for(int j=startC;j<startC+3;j++) {
				if(i==r && j==c) continue;
				if(map[i][j]== map[r][c]) return false;
			}
		}
		return true;
	}
	
}