[Java Algorithm] 스도쿠 BOJ #2239

문제

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

 

내 문제 풀이

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

public class Main {
	
	static int[][] map = new int[9][9];
	static List<int[]> empty = new ArrayList<>(); // 빈 칸 리스트
	
	public static void sudoku(int cnt) {
		if(cnt == empty.size()) { // 빈 칸 다 채우면 (게임 종료 처리)
			for(int i = 0; i < 9; i++) {
				for(int j = 0; j < 9; j++) {
					System.out.print(map[i][j]);
				}
				System.out.println();
			}
			System.exit(0);
		}
		
		// 현재 위치 (빈 칸)
		int x = empty.get(cnt)[0];
		int y = empty.get(cnt)[1];
		// 현재 위치하는 사각형의 시작점
		int startX = x / 3 * 3;
		int startY = y / 3 * 3;
		// x, y 지점의 상하좌우 및 사각형 안에 있는 숫자들을 체크
		boolean[] check = new boolean[9];
		
		for(int i = 0; i < 9; i++) {
			if(map[x][i] > 0) check[map[x][i]-1] = true; // 좌우
			if(map[i][y] > 0) check[map[i][y]-1] = true; // 상하
		}
		for(int i = startX; i < startX+3; i++) {
			for(int j = startY; j < startY+3; j++) {
				if(map[i][j] > 0) check[map[i][j]-1] = true; // 사각형 안
			}
		}
		
		for(int i = 0; i < 9; i++) {
			if(!check[i]) { // 사용되지 않은 수 발견 시, 현재 위치에 해당하는 수를 넣어보고 sudoku 재귀 호출 (모든 경우의 수 따져보기)
				map[x][y] = i+1;
				sudoku(cnt+1);
				map[x][y] = 0;
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		for(int i = 0; i < 9; i ++) {
			String str = in.readLine();
			for(int j = 0; j < 9; j++) {
				map[i][j] = str.charAt(j) - '0';
				if(map[i][j] == 0) empty.add(new int[]{i, j});
			}
		}
		
		sudoku(0);
	}
}

👉 구현 문제

주어진 입력을 받으면서, 0이 입력될 시 empty라는 List에 좌표를 추가했고,

sudoku라는 메소드를 만들어서 게임을 진행하도록 해주었다.

 

check라는 boolean 타입의 크기 9인 배열을 만들어 주고, 0번째 인덱스는 1, 1번째 인덱스는 2, 이런 식으로

숫자와 인덱스를 매핑하여 1부터 9까지의 숫자 중 어떤 숫자가 사용되었고 어떤 숫자가 사용되지 않았는지를 체크했다.

 

empty 리스트의 첫 번째 좌표부터 차례대로 탐색을 진행해주었는데,

x, y에 해당하는 좌표 값을 담고, 간단한 연산을 통해 x, y좌표가 속하는 사각형의 시작 좌표도 구해주었다.

(x와 y값을 각각 3으로 나눈 뒤 다시 3을 곱해주면 3*3 크기의 사각형의 시작 좌표를 구할 수 있다.)

 

두 개의 for문을 이용하여 x, y 좌표의 상, 하, 좌, 우에 있는 숫자들 및

x, y 좌표가 속하는 사각형에 있는 숫자들을 조사하여 check에 표시했다.

 

그리고 check 배열을 순회하며 사용되지 않은 수 발견 시,

그 수를 현재 x, y 좌표에 넣어준 뒤 sudoku의 파라미터 cnt를 1 증가시켜 재귀호출했다.

그리고 다시 x, y 좌표에 0을 넣어서, 다른 값을 넣는 경우도 생각해줄 수 있도록 했다.

 

위와 같은 반복을 계속하다가 빈 칸을 모두 채웠다면, 스도쿠에 성공했다는 의미이므로

결과를 출력하고 시스템을 종료시켰다.

 

+ 문제에서 답이 여러 개일 경우 사전적으로 앞서는 것을 출력하라고 하였는데,

어차피 가장 좌측 상단부터 시작하여 작은 수부터 채워넣기 때문에

이 부분은 따로 체크하지 않아도 괜찮다.

 

💡 피드백

• 처음에는 exit 메소드를 사용하지 않고, return 하는 것으로 코드를 작성했는데,
  왜인지 모르겠지만 자꾸 출력초과가 나더라,,!!
  그래서 구글링 해보니까 exit 사용해야 한다고 해서ㅜ 그렇게 바꿨더니 통과했다..
  사실 아직도 이유를 잘 모르겠어서... 계속 한 번 찾아봐야겠다.