[백준/JAVA] 2239_스도쿠

백준🔗

2239번: 스도쿠

 

문제

 

 

간단 풀이

아주아주 오래만에 풀어보는.. 백트래킹!!

 

그래서 백트래킹 개념을 일단 정리하고 가보자.

백트래킹

여러 가지 선택지 옵션들이 존재하는 상황에서 한 가지를 선택한다.
선택이 이루어지면 새로운 선택지들의 집합이 생성된다.
이런 선택을 반복하다 보면 최종 상태에 도달한다.
즉, 해결책으로 이어질 것 같지 않으면 더이상 그 경로를 따라가지 않음으로써 시도 횟수를 줄여나가는 방식 (가지치기)

백트래킹 vs DFS

DFS는 모든 경로를추적하고, 백트래킹은 불필요한 경로를 조기에 차단한다.
DFS를 하기에 경우의 수가 너무 많은 경우 백트래킹 알고리즘을 사용해서 경우의 수를 줄일 수 있지만, 이 역시도 최악의 경우에는 여전히 지수 함수의 시간이 소요될 수 있다.

 

개념은 이렇지만 구현에 어려움을 좀 겪다가 다른 코드를 참고해서 풀 수 있었다..!

 

처음에 입력을 받을 때 아직 숫자가 채워지지 않은 칸들을 list에 따로 저장해준다.

이후에 list에 있는 각 칸들에 대해 행, 열, 3*3 사각형에 없는 수들, 즉 해당 칸에 들어갈 수 있는 후보들을 구해주고, 작은 수부터 선택하면서 다음 칸으로 넘어간다. 

이로써 모든 경우를 탐색하지 않고도 가지치기를 통해 적은 경우만 탐색해서 답을 구할 수 있다.

 

이 때 주의할 점은, 최종 답이 여러 개일 때도 사전순으로 앞서는 것을 하나만 출력해야 하기 때문에 backtracking이 처음 기저 조건에 걸렸을 때 바로 결과를 출력하고 프로그램을 종료시켜 주어야 했다.

 

코드

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int[][] map;
	static List<Point> list;

	public static void main(String[] args) throws Exception {
		map = new int[9][9];
		list = new ArrayList<>();
		for (int r = 0; r < 9; r++) {
			String input = br.readLine();
			for (int c = 0; c < 9; c++) {
				map[r][c] = input.charAt(c) - '0';
				if (map[r][c] == 0) {
					list.add(new Point(r, c));
				}
			}
		}
		backtracking(0);
		br.close();
		bw.close();
	}

	static class Point {
		int r, c;

		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	static void backtracking(int idx) throws IOException {
		// 기저조건
		if (idx == list.size()) {
			for (int r = 0; r < 9; r++) {
				for (int c = 0; c < 9; c++) {
					bw.write(Integer.toString(map[r][c]));
				}
				bw.write('\n');
			}
			bw.flush();
			System.exit(0); // 다른 경우 더이상 탐색하지 않도록 완전 종료!
		}
		// 유도조건
		Point cur = list.get(idx);
		// 들어갈 수 있는 후보들 찾기
		boolean[] nums = new boolean[10];
		// 1) 행
		for (int c = 0; c < 9; c++) {
			if (map[cur.r][c] != 0) {
				nums[map[cur.r][c]] = true;
			}
		}
		// 2) 열
		for (int r = 0; r < 9; r++) {
			if (map[r][cur.c] != 0) {
				nums[map[r][cur.c]] = true;
			}
		}
		// 3) 3*3박스
		for (int r = cur.r / 3 * 3; r < cur.r / 3 * 3 + 3; r++) {
			for (int c = cur.c / 3 * 3; c < cur.c / 3 * 3 + 3; c++) {
				if (map[r][c] != 0) {
					nums[map[r][c]] = true;
				}
			}
		}
		// 작은 수부터 선택해서 채워보기
		for (int i = 1; i <= 9; i++) {
			if (!nums[i]) {
				map[cur.r][cur.c] = i;
				backtracking(idx + 1);
				map[cur.r][cur.c] = 0; // 원상복구
			}
		}
	}
}

 

참고 자료

[BOJ/백준] 2239. 스도쿠 (Java)