BOJ 2580 스도쿠 Java

BOJ 2580 스도쿠 Java

 

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

2580번: 스도쿠

 

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

public class Main {
	static int[][] grid = new int[9][9];
	static List<int[]> list = new ArrayList<>();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < 9; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++) {
				grid[i][j] = Integer.parseInt(st.nextToken());
				if(grid[i][j] == 0) {
					list.add(new int[] {i, j});
				}
			}
		}
		
		if(list.size() > 0)
			solve(0);
		
	} // main
	
	static void solve(int idx) {
		if(idx == list.size()) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(grid[i][j] + " ");
				}
				System.out.println();
			}
			System.exit(0);
		}
		int i = list.get(idx)[0], j = list.get(idx)[1];
				
		for (int num = 1; num <= 9; num++) {
			if(!isSuccess(i, j, num)) continue;
			
			grid[i][j] = num;
			solve(idx+1);
			grid[i][j] = 0;
		}
		
	} // solve
	
	static boolean isSuccess(int r, int c, int num) {
		// 가로 세로
		for (int i = 0; i < 9; i++) {
			if(grid[i][c] == num || grid[r][i] == num) return false;
		}
		
		// 사각형
		r = (r/3) * 3;
		c = (c/3) * 3;
		for (int i = r; i < r+3; i++) {
			for (int j = c; j < c+3; j++) {
				if(grid[i][j] == num) return false;
			}
		}
		return true;
	}
}

 

풀고나서 코드가 깔끔하지 않아서 마음에 들지 않았다..

깔끔한 다른 코드를 참고해서 리팩토링 했다 ㅎ

 

깨달은 것은..

main 끝날 때 System.exit(0) 호출되는 점을

함수에 적용해서 바로 끝내버리기..

 

나는 스도쿠 답을 하나 찾으면 boolean 으로 이미 찾은 경우 계속 return 하는 방식으로 해 시간이 오래 걸렸다

 

그리고 사각형 체크를

규칙을 못찾겠어서

0~2는 0

3~5는 3

6~8은 6

이렇게 매핑했는데

 

r = (r/3) * 3

이라는 놀라운 규칙이 있었다

바보..