2580

 

스도쿠 : https://www.acmicpc.net/problem/2580

참고 : https://infodon.tistory.com/64

 

 

최초 접근 방법 

1. 0의 위치를 Q에 모두 저장.

2. 좌표가 포함된 9자리 및 행/렬을 탐색하여 0을 찾은 뒤, 없는 숫자를 채워줌.

3. Q를 통해 1,2를 반복함. 

 

문제점 : 문제가 간단한 경우, 답을 찾을 수 있지만 0이 많아지는 경우 2번에서 답을 계속 찾지 못해 무한루프에 빠져버림. 기본적으로 스도쿠를 별로 해보지 않아서 답을 찾는 과정에 대한 이해가 부족했다.

(9칸 및 행/렬을 체크하면 반드시 0에 들어갈 값을 알 수 있을거라 생각한것이 오류)

 

참조사이트에서 확인한 바와 같이, 어떤 값을 연속적으로 대입하여 답을 찾아가는 과정에서는 DFS를 사용하는 것이 좋은 방법으로 보인다.

 

 

참조 사이트를 통해 알아낸 방법.

1. map을 순차적으로 순회하여 0인 지점을 찾아냄

2. 1-9사이의 숫자 중, 해당좌표가 포함된 9칸 및 행렬과 중첩되지 않는 숫자를 넣고 다음칸으로 넘어감.

3. 1-2를 반복하여 마지막 위치를 넘어가면 map을 출력하고 프로그램을 종료함.

 

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

public class Main {

	static boolean DBG = false;

	static int[][] map;
	static int LEN = 9;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		map = new int[LEN][LEN];
		for (int i = 0; i < LEN; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < LEN; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		flag=false;
		dfs(0, 0);
	}
	static boolean flag;
	private static void dfs(int x, int y) {
		
		
		if(flag)//답을 찾은 경우, 프로그램 종료( 해당 라인이 없는 경우 AC되지 않음, 답을 찾은 뒤에도 프로그램이 종료되지 않아 timeout되는 것으로 추측됨).
			return;
		
		if ( y == 9) { // 오른쪽 끝에 도달, 다음 행의 첫번째 열로 넘어감.
			dfs(x + 1, 0);//dfs(x + 1, y) 와 같이 인자를 잘못 넘겨주는 경우를 주의.
			return;
		}

		if (x == 9) {// 마지막 행을 넘어가면 정답
			for (int[] arr : map) {
				for (int v : arr)
					System.out.print(v + " ");
				System.out.println();
			}
			flag=true;//나머지 루프를 종료.
			return;
		}

		if (map[x][y] == 0) {

			for (int i = 1; i <= 9; ++i) {
				if (check(x, y, i)) {
					map[x][y] = i;
					dfs(x, y + 1);
				}
			}
			// 빈칸을 1-9까지 시도해봤으나 채우지 못하는 경우, 즉 문제에 답을 찾을 수 가 없는 case에 해당 값을 초기화 후 종료.
			if(DBG) 
				System.out.println("map is wrong");
			map[x][y] = 0;
			return;
		}

		// x,y가 0이 아닌 경우 다음칸 진행.
		dfs(x, y + 1);
	}

	// 같은 값이 있으면 false, 없으면 true
	private static boolean check(int x, int y, int value) {

		// x축 확인
		for (int i = 0; i < LEN; i++) {
			if (map[i][y] == value)
				return false;
		}
		// y축 확인
		for (int i = 0; i < LEN; i++) {
			if (map[x][i] == value)
				return false;
		}

		// 큰 정사각형의 시작점 및 종점을 구한다.
		int sx = x / 3 * 3;
		int sy = y / 3 * 3;
		int ex = sx + 3;
		int ey = sy + 3;

		for (int i = sx; i < ex; i++) {
			for (int j = sy; j < ey; j++) {
				if (map[i][j] == value)
					return false;
			}
		}

		return true;
	}
}