[BOJ 2580] 스도쿠(Java)

---

문제

스도쿠

---

문제 해설

문제에서 주어진 요구사항대로 스도쿠라는 게임을 구현하면 되는 문제입니다. 주어진 board에서 0인 곳이 비어있는 자리이며 이곳을 스도쿠 공식에 맞게 숫자를 대입해야 합니다.
요구되는 로직은 다음과 같습니다.

• 해당 좌표의 행을 검사하는 메소드가 필요합니다.
• 해당 좌표의 열을 검사하는 메소드가 필요합니다.
• 해당 좌표의 3x3 그룹을 검사하는 메소드가 필요합니다.

또 빈 자리가 많아지면 시간복잡도가 기하급수적으로 증가하기 때문에 적절한 가지치기가 필요합니다.

저의 경우 빈자리를 전부 ArrayList에 담고arr, 재귀적으로 자리를 채울 수 있는 메소드를 만든 뒤back(), 하나의 경우라도 완성하게 되면 재귀 함수를 종료하게 만들었습니다if(back(depth + 1)).

최종적으로 프로그램의 순서도는 다음과 같습니다.

1. 주어진 input을 2차원 int 배열에 담고, 빈 자리라면 해당 좌표를 ArrayList에 담습니다.
2. 재귀 메소드에 진입합니다. 기저 조건은 모든 빈자리가 채워졌을때 입니다.
3. 빈자리의 좌표를 꺼내어 1부터 9까지 순차적으로 넣을 수 있는 숫자를 검사합니다.
4. 숫자를 넣을 수 있다면 해당 board에 숫자를 삽입하고 깊이+1 한 뒤, 3을 반복합니다.
5. 기저 조건을 만족하면 종료합니다.

---

풀이 코드

package 알고리즘스터디;

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

public class BOJ2580_스도쿠 {
	static int[][] map = new int[9][9];
	static ArrayList<int[]> arr = new ArrayList<>();

	// 행 검사
	static boolean checkRow(int x, int y, int num) {
		for (int i = 0; i < 9; i++) {
			if (map[x][i] == num)
				return false;
		}
		return true;
	}

	// 열 검사
	static boolean checkCol(int x, int y, int num) {
		for (int i = 0; i < 9; i++) {
			if (map[i][y] == num)
				return false;
		}
		return true;
	}

	// 3x3 사각형 검사
	static boolean checkSqu(int x, int y, int num) {
		for (int i = (x / 3) * 3; i < (x / 3) * 3 + 3; i++) {
			for (int j = (y / 3) * 3; j < (y / 3) * 3 + 3; j++) {
				if (map[i][j] == num)
					return false;
			}
		}
		return true;
	}

	// 백트래킹
	static boolean back(int depth) {
		if (depth == arr.size())
			return true;
                int x = arr.get(depth)[0];
		int y = arr.get(depth)[1];
		for (int i = 1; i <= 9; i++) {
			if (checkCol(x, y, i) && checkRow(x, y, i) && checkSqu(x, y, i)) {
				map[x][y] = i;
				if(back(depth + 1)) {
					return true;
				}
				map[x][y] = 0;
			}
		}
		return false;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 0)
					arr.add(new int[] { i, j });
			}
		}
		back(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);
		br.close();
	}

}

---