백준 2580, 2239 스도쿠 (Java)

1. 문제 링크

2580번: 스도쿠

2239번: 스도쿠

 

2. 문제 및 입출력예제

 

3. 문제 풀이

두 문제가 입출력의 공백 차이 뿐이라 함께 가져왔다.

dfs 느낌으로 이 숫자일 때 다음 숫자가 가능한지 그 다음은 가능한지... 의 순서로 코드를 진행한다.

 

4. 코드

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

public class Main {
	static class Point{
		int x;
		int y;
		int num;
		public Point(int x, int y, int num) {
			super();
			this.x = x;
			this.y = y;
			this.num = num;
		}
	}
	static int[][] map;
	static int idx;
	static ArrayList<Point> blank;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
	
		blank = new ArrayList<>();
		map = new int[9][9];
		for(int i=0;i<9;i++) {
			String[] split = br.readLine().split("");
			for(int j=0;j<9;j++) {
				map[i][j] = Integer.parseInt(split[j]);
				if(map[i][j] == 0) {
					blank.add(new Point(i, j, 0));
				}
			} 
		}
		
		sudoku(0);
		
		for(int i=0;i<9;i++) {
			for(int j=0;j<9;j++) {
				sb.append(map[i][j]+"");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	
	private static boolean sudoku(int cnt) {
		if(cnt == blank.size()) {//전부 다 채웠다면
			return true;
		}
		Point p = blank.get(cnt);
		int x = p.x;
		int y = p.y;
		for(int i=1;i<10;i++) {
			if(possible(map, x, y, i)) {
				map[x][y] = i;
				if(sudoku(cnt+1)) return true;
				map[x][y] = 0; //끝까지 못 가면 초기화
			}
		}
		
		return false;
	}


	private static boolean possible(int[][] map, int x, int y, int num) {
		int len = map.length;
		int sero = x/3;
		int garo = y/3;
		
		//가로, 세로
		for(int i=0;i<len;i++) { //이미 있는 숫자라면
			if(map[x][i] == num) return false;
			if(map[i][y] == num) return false;
		}
		
		for(int i=0;i<3;i++) {
			for(int j=0;j<3;j++) {
				if(map[sero*3+i][garo*3+j] == num) {
					return false;
				}
			}
		}
		
		return true;
	}
}