[알고리즘] Java / 백준 / 스도쿠 / 2580

[알고리즘] Java / 백준 / 스도쿠 / 2580

문제

문제 링크

접근 방식

1. 1행 1열에서 스도쿠 함수를 실행한다
2. 만약 현재 값이 0이면 1부터 9까지 번호 중 현재 위치에 들어갈 수 있는 각각의 수를 현재 값에 저장하고 다음 열의 스도쿠 함수를 실행시킨 후 다시 현재 값을 0으로 바꾼다
3. 현재 값이 0이 아니면 바로 다음 열의 스도쿠 함수를 실행한다
4. 열이 10을 넘기면 행을 올리고 열을 다시 1로 초기화한다
5. 행이 10이면 스도쿠맵을 출력하고 시스템을 종료한다

코드

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

public class Main_2580_baekjoon {

	static int map[][];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new int[10][10];
		
		for(int i=1;i<=9;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1;j<=9;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		sudoku(1,1);
	}
	
	public static void sudoku(int r, int c) {
//		System.out.println("r:" +  r + " c:" + c);
		if(r==10) {
			StringBuilder sb = new StringBuilder();
			for(int i=1;i<=9;i++) {
				for(int j=1;j<=9;j++) {
					sb.append(map[i][j] + " ");
				}
				sb.setLength(sb.length()-1);
				sb.append("\n");
			}
			System.out.print(sb);
			System.exit(0);
		}
		else if(c == 10) {
			sudoku(r+1,1);
			return;
		}
		
		if(map[r][c]==0) {
			for(int i=1;i<=9;i++) {
				if(isPromising(r,c,i)) {
					map[r][c] = i;
					sudoku(r,c+1);
					map[r][c] = 0;
				}
			}
			return;
		}
		sudoku(r,c+1);
	}
	
	public static boolean isPromising(int r, int c, int value) {
		
		for(int i=1;i<=9;i++) {
			if(map[r][i] == value) return false;
		}
		
		
		for(int i=1;i<=9;i++) {
			if(map[i][c] == value) return false;
		}
		
		int row = (r-1) - (r-1)%3 + 1;
		int col = (c-1) - (c-1)%3 + 1;
		
		for(int i= row;i<=row+2;i++) {
			for(int j= col;j<=col+2;j++) {
				if(map[i][j] == value) return false;
			}
		}
		
		return true;
	}

}