[백준/java] 2239. 스도쿠

문제 링크 - https://www.acmicpc.net/problem/2239

🌱 문제

🌱 풀이

• 0인 칸에 스도쿠의 규칙을 만족하는 선에서 넣을 수 있는 숫자(1~9)를 전부 넣어보는 완전탐색(?)처럼 풀었다.
• arr[][]을 돌면서 0인 좌표를 리스트에 담아놓는다.
• 재귀함수로 리스트의 인덱스를 인자로 보내고, 리스트에 있는 좌표에 수를 전부 할당하면 배열을 main함수를 종료한다. (답이 여러개라면 사전식으로 앞서는 것을 출력해야 하기 때문에)

• 0인 좌표에 수를 할당하는 방식은 아래와 같은 방법을 이용해 찾는다.
  0. boolean 배열을 선언하여, 이미 사용된 수를 true로 체크한다.
  1. 해당 좌표와 같은 열에서 사용된 수를 체크한다.
  2. 해당 좌표와 같은 행에서 사용된 수를 체크한다.
  3. 해당 좌표가 해당하는 3x3(스도쿠 규칙) 배열에서 사용된 수를 체크한다.
• check배열을 돌면서 사용하지 않은 수를 현재 좌표에 할당하고 다음 재귀함수로 넘어간다.

주의할점

	boolean check[] = new boolean[10]; // 여기 지역으로 해야함!!!!!!!! 

• 수의 사용 여부를 확인하는 check배열을 지역이 아닌 전역으로 선언해서 엄청 헤맸다.
• 함수를 돌다가, 답이 될수 없는 경우임을 확인하고 이전 인덱스의 상태로 돌아갈 경우, 그때까지의 check 상태를 알고 있어야 하기 때문에 지역변수로 선언해서 관리해줘야 한다.!!!

🌱 코드

package boj;

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

//2239. 스도쿠 
public class boj_2239 {
	static class Point {
		int r, c;
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + "]";
		}
	}

	static int arr[][];
	static int listSize;
	static boolean check[];
	static ArrayList<Point> list;
	static ArrayList<Integer> nums;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		arr = new int[9][9];
		list = new ArrayList<Point>();
		nums = new ArrayList<Integer>();

		String s;
		for (int i = 0; i < 9; i++) {
			s = br.readLine();
			for (int j = 0; j < 9; j++) {
				arr[i][j] = s.charAt(j) - '0'; // 숫자로 변환
			}
		}
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (arr[i][j] == 0) {
					list.add(new Point(i, j));
				}
			}
		}
		listSize = list.size();
		func(0);
	}

	public static void func(int index) {
	
		if (index == listSize) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(arr[i][j]);
				}
				System.out.println();
			}
//			return;
			System.exit(0); // main 종료 
		}

		Point cur = list.get(index); // 현재 숫자를 채울 좌표
		boolean check[] = new boolean[10]; // 여기 지역으로 해야함!!!!!!!! 

		// 같은 열 살펴보기
		for (int i = 0; i < 9; i++) {
			int num=arr[i][cur.c];
			if(num!=0 && check[num]==false)
				check[num]=true;
		}

		// 같은 행 살펴보기
		for (int i = 0; i < 9; i++) {
			int num=arr[cur.r][i];
			if(num!=0 && check[num]==false)
				check[num]=true;
		}

		// 현재 칸이 속한 3x3배열 살펴보기
		int startR = cur.r/3 * 3;
		int startC = cur.c/3 * 3;
		for (int i = startR; i < startR + 3; i++) {
			for (int j = startC; j < startC + 3; j++) {
				int num=arr[i][j];
				if(num!=0 && check[num]==false)
					check[num]=true;
			}
		}

		for (int i = 1; i <= 9; i++) {
			if (check[i] == false) {
				arr[cur.r][cur.c] = i;
				func(index + 1);
				arr[cur.r][cur.c] = 0;
			}
		}

	}

}