[BOJ] 2580 스도쿠 Java 풀이

 

 

BOJ 2580 스도쿠 - 1

BOJ 2580 스도쿠 - 2

 

어렸을 때 한 번씩 해봤을 법한 게임이다. 간단한 프로그래밍으로 답을 찾아낼 수 있을 거란 생각은 못해봤는데 신기하다. 

여하튼 문제를 보면 몇 군데에 구멍이 뚫려있고, 그 안에 조건을 만족시키는 수를 넣어야 하는데 조건을 모두 만족시키려니 조금 머리가 아프다. 1) 가로줄에 유일한 숫자여야하고, 2) 세로줄에 유일한 숫자여야 하고, 3) 작은 사각형 안에서 유일한 숫자여야 하는 조건을 만족시켜야 하는데 구멍에 값을 하나 채워놓았는데 가로줄, 세로줄, 작은 사각형 안에 다른 구멍이 있다면 어떻게 해야할까 조금 막막하다.

다만 최근 백트래킹 문제를 집중적으로 몇 개 접했다보니, 순간 DFS와 백트래킹은 뇌리에 스쳤다. 결국 자리에 1~9를 모두 넣어보는데, 넣을 때마다 조건에 부합하는지를 체크하고 넣어주면 된다. 모두 넣어보는게 시간복잡도상 괜찮을까라는 생각이 드는데 9 X 9 보드에서 각 칸에서 1 ~ 9를 넣어봐야 9 * 9 * 9면 생각보다 크지 않다. 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static int[][] map = new int[9][9];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for(int i = 0; i < 9; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < 9; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		solve(0, 0);
		
	}
	
	private static void solve(int row, int col) {
//		System.out.println(row+","+ col);
		
		// 모든 열을 처리했으면 다음 행 수행 
		if(col == 9) {
			solve(row + 1, 0);
			return;
		}
		// 모든 수를 처리했으면 출력 후 종료
		if(row == 9) {
			StringBuilder sb = new StringBuilder();
			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.toString());
			System.exit(0);
		}
		
		// 현재 위치가 값을 채워나가야 하는 값이면 1 ~ 9 까지 넣어보고 검사
		if(map[row][col] == 0) {
			for(int i = 1; i <= 9; i++) {
				if(isPossible(row, col, i)) {
					map[row][col] = i;
					solve(row, col+1);
				}
			}
			
			map[row][col] = 0;
			return;
		}
		solve(row, col + 1);
	}
	
	private static boolean isPossible(int row, int col, int value) {
		for(int i = 0; i < 9; i++) {
			if(map[row][i] == value || map[i][col] == value) {
				return false;
			}
		}
		
		int smallRow = (row / 3) * 3;
		int smallCol = (col / 3) * 3;
		
		for(int i = smallRow; i < smallRow + 3; i++) {
			for(int j = smallCol; j < smallCol + 3; j++) {
				if(map[i][j] == value) return false;
			}
		}
		
		return true;
	}

}

 

두 가지 메소드를 만들어 풀이를 진행했다. 1~9를 넣어보는 solve, 모든 조건에 부합하는 지를 확인하는 isPossible이다.

먼저, isPossible은 해당 자리의 가로줄, 세로줄, 작은 사각형 범위 안에서 유일한 값이면 true, 아니면 false를 리턴한다. 크게 어려운 부분은 없다.

다음으로, solve에서는 먼저 목적지?(return을 하거나 새로운 재귀함수를 호출해야 하는 경우)에 도착한 경우 처리를 해주는 부분이 등장한다. 열을 끝까지 돌아 다음 행으로 넘어가거나, 보드 내 모든 영역의 탐색이 끝난 경우이다. (개인적으로 풀이를 할 때는 주로 중간~마지막에 코드를 작성하거나 먼저 대략적으로 작성하되 추후에 손을 보며 코드 작성한다.) row, col로 탐색하며 값을 채워야 하는 자리라면 반복문을 통해 1~9의 숫자를 isPossible에 넣어 가능한지 탐색하고, true이면 해당 값을 자리에 넣어주고 다음 자리의 재귀 함수를 호출한다.

풀이의 핵심은 그 아래 부분인데, 1~9에서 넣을 수 있는 수를 넣고 재귀함수를 호출한 뒤 다시 자리에 0을 넣고 return을 해준다. 이유는 조건을 확인하는 영역 안에 빈 칸이 또 있어서, 값을 막 채워넣을 수 없는 경우 때문이다. 예를 들어 먼저 빈 칸 X에 (1, 9가 들어갈 수 있는 자리에)1이라는 특정 수를 넣었는데 같은 작은 사각형 안에 다른 빈 칸 Y이 존재하고, 그 빈 칸 Y에 반드시 1이 들어가야 하는 경우가 있을 수 있다. 만약 그렇다면 먼저 넣었던 X 빈칸을 9로 다시 바꿔주어야 하는데 이 경우에는 반복문을 통해 재귀를 돌다가 답을 찾지 못해 다시 돌아와서 9를 넣어주며 해결이 될 것이다. 

반대로 빈 칸 X에 9를 넣었는데 같은 작은 사각형 안에 다른 빈 칸 Y가 9를 넣어야 해서 빈 칸 X에 다시 1을 넣어 주어야 하는 경우가 있을 수 있다. 반복문이 1부터 차례대로 9까지 값을 넣는데 1을 다시 넣어주려면 다시 그 자리에 solve 함수가 돌아왔을 때 반복문을 다시 돌 수 있도록 만들어 줘야 하기 때문에 0을 넣어준다. 재귀 함수를 돌며 값을 낼 수 없는 경우 return을 통해 다시 인덱스를 돌아가지만, 그 과정에서 이미 값을 넣어버린 것은 0으로 돌아오지 않는다. (개인적으로 이 부분이 이 문제 풀이에 있어 핵심 부분이라 느꼈다. 여기서 좀처럼 해결하기 어려웠는데 익숙해진다면 많은 문제에 도움이 될 것 같아 이 부분을 이해하는 게 중요하다고 생각한다.)