[BOJ/JAVA] 백준 2580번 : 스도쿠

2580번: 스도쿠

---

 

• 생각

백트래킹(0으로 되돌리는 작업)을 하지않고 했다가 고생좀 했다.. 0이 발견되면 1~9까지 다 넣어보면서 행, 열, 3X3 모두 체크해주면서 true가 반환되면 해당 값을 넣어준뒤 c를 +1해주면서 재귀를 돈다. 여기서 다른 값이 안될 경우가 있기 때문에 가다가 아무작업도 못하고 되돌아올 경우 다시 0으로 돌려주어야 한다.

 

• 코드

정답 코드 : 백트래킹으로 구현한 코드이다.

 

import java.io.*;
import java.util.*;

public class Main {

	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		array = new int[9][9];
		sb = new StringBuilder();

		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}

		Sudoku(0, 0);

	}

	static void Sudoku(int r, int c) {

		if (c == 9) {
			sb.append("\n");
			Sudoku(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(array[i][j] + " ");
				}
				System.out.println("");
			}
			System.exit(0);
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Possible(r, c, i)) {
					array[r][c] = i;
					Sudoku(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			Sudoku(r, c + 1);
		}
	}

	static boolean Possible(int r, int c, int value) {

		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}

}

 

나중 코드 : 백트래킹으로 구현한 코드이다.

 

import java.io.*;
import java.util.*;

public class Main {
	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		dfs(0, 0);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		array = new int[9][9];
		sb = new StringBuilder();
		
		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}

	}

	static void dfs(int r, int c) {

		if (c == 9) {
			dfs(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(array[i][j] + " ");
				}
				sb.append("\n");
			}
			System.out.println(sb);
			System.exit(0); // 이렇게 바로 끝내줘야지 시간초과가 나지 않음
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Sudoku(r, c, i)) {
					array[r][c] = i;
					dfs(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			dfs(r, c + 1);
		}
	}

	static boolean Sudoku(int r, int c, int value) {
		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}
}