[BAEKJOON 백준] 2239 스도쿠

www.acmicpc.net/problem/2239

2239번: 스도쿠

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

 

 

DFS 방식으로 스토쿠를 만들어내는 방식으로 작성했다.

 

DFS를 이용을 해서 각 각의 위치 값을 Point로 정해서 배열을 만들었다.

 

DFS를 진행하기전에 대각선과 가로, 세로에 같은 수가 있다면 넘어갈 수 있게 체크를 한다.

 

그렇게 DFS가 0의 갯수가 arrlist와 갯수가 같아지면 종료를 하게 작성을 했다.

 

 

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

public class Main {
	private static class Point {
		int x, y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

	}

	private static int N = 9;
	private static int arr[][];
	private static ArrayList<Point> arrlist;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		arr = new int[N][N];
		arrlist = new ArrayList<Point>();
		for (int i = 0; i < N; i++) {
			String s = bf.readLine();
			for (int j = 0; j < N; j++) {
				arr[i][j] = s.charAt(j) - '0';
				if (arr[i][j] == 0) {
					arrlist.add(new Point(i, j));
				}
			}
		}
		sdoku(0);

		
		System.out.println(result);
	}
	private static String result="";
	private static void sdoku(int cnt) {
		// TODO Auto-generated method stub
		if (cnt == arrlist.size()) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					result+=arr[i][j];
				}
				result+="\n";
			}
			System.out.println(result);
			System.exit(0);
		}
		Point p = arrlist.get(cnt);
		for (int i = 1; i <= N; i++) {
			arr[p.x][p.y] = i;
			if (row(p.x)) {
				continue;
			}
			if (column(p.y)) {
				continue;
			}
			if (matrix(p)) {
				continue;
			}
			sdoku(cnt + 1);
		}
		arr[p.x][p.y]=0;

	}
	private static boolean matrix(Point p) {
		// TODO Auto-generated method stub
		boolean visit[] = new boolean[N + 1];
			for (int i = (p.x / 3) * 3; i < ((p.x / 3) +1) *3; i++) {
				for (int j = (p.y / 3) * 3; j < ((p.y / 3) +1) *3; j++) {
					if (arr[i][j] > 0) {
						if (visit[arr[i][j]]) {
							return true;
						} else {
							visit[arr[i][j]] = true;
							
						}
					}
				}
			}
		return false;
	}

	private static boolean column(int y) {
		// TODO Auto-generated method stub
		boolean visit[] = new boolean[N + 1];
		for (int i = 0; i < N; i++) {
			if (arr[i][y] > 0) {
				if (visit[arr[i][y]]) {
					return true;
				} else {
					visit[arr[i][y]] = true;

				}
			}
		}
		return false;
	}

	private static boolean row(int x) {
		// TODO Auto-generated method stub
		boolean visit[] = new boolean[N + 1];
		for (int i = 0; i < N; i++) {
			if (arr[x][i] > 0) {
				if (visit[arr[x][i]]) {
					return true;
				} else {
					visit[arr[x][i]] = true;

				}

			}
		}
		return false;
	}
}