[알고리즘] 스도쿠 (백트래킹) : 백준 2580 자바 / 사람과 컴퓨터의 관점

조금 원론적인 이야기를 하자면 .. 스도쿠를 해봤다면 알겠지만 인간이 이 게임을 할때 사실 어려운 문제는 간단하지 않다.. 여러 방면에서 공식을 대입해가면서 풀어야하고 초보자의 경우에는 실수도 많이 튀어나와서 연필로 수도쿠를 하고 있었다면 지우개로 지우다가 종이가 너덜너덜(?) 해지는 케이스가 있을 때가 있다.

 

사람의 두뇌는 사실상 모든 케이스를 판별하기보다는 공식에 혹은 경험에 의거하여 결론을 도출하는 경향이 크다. 하지만 컴퓨터의 경우는 다르다. 컴퓨터는 먼저 매우 빠르다.(!!) 그 빠름의 강점을 이용해서 모든 케이스를 판별하는 것이 가장 일반적인 혹은 기본적인 활용 방법 중 하나이다. 우리가 코딩을 할때는 조건문과 반복문을 통해서 어떤 코드를 짜는데 사실 그게 다이다.. 빠른 컴퓨터를 이용해서 빠르게 반복해서 빠르게 조건을 판별해서 빠르게 도출하는 것이다. 우리가 짜는 코드를 컴퓨터가 빠르게 돌리는 것 뿐이다. 생각하는게 아닌, 빠른거다. 매우. 

 

그 강점을 이용하기 때문에 사람의 생각과 같은 경험에 의거한 방법론을 대입하면 오히려 복잡해지는 경우가 있다. 스도쿠를 해봤으면 알겠지만 케이스마다 어떤 공식이 있다. 예를 들어 3을 기준으로 뭐 가로줄 세로줄에 존재하지 않고 머시기머시기.. 어떤 복잡한 꿀팁들이 많다. 하지만 우리가 코드로 스도쿠를 짤때 그런 공식들을 대입했다가는 코드가 산으로 간다. 우리는 컴퓨터를 믿고 코드를 저질러야(?) 한다. 사람에게 "야 이 모든 케이스를 판별해서 종이에 써서 나한테 줘" 이런 과제가 나온다면 십중팔구 기분이 좋지않다.. 하지만 운영체제만 배웠어도 컴퓨터는 그게 일상이고 컴퓨터의 가~~장 기본적인 역할이다. 반복하는 것, 케이스를 판별하는 것.. 모든 케이스를 판별하게 냅두자. 그것이 코드를 짜는 사람의 입장에서도, 컴퓨터 입장에서도 훨씬 쉬운일이 될것이다. 

 

이 문제도 그런 마인드로 접근해야한다. 오히려 스도쿠를 즐겨하던 사람은 독이 될수도 있는 문제이다. 사람이 쓰는 공식들을 코드에 대입하려는 순간 답이 없어진다. 문제의 의도만 파악해도 그런 문제는 아니라는 걸 이제 알아야한다. 수도쿠의 기본적인 룰만 적용을 하자.

 

그것은 어떤 요소에 값은 가로줄, 세로줄, 해당하는 3x3 박스안에서 중복되지만 않으면 된다는 점. 이것만 조건으로 삼아서 dfs를 진행하면 된다. 즉! 백트래킹의 조건으로 위의 조건을 주는 것이다.

 

그러면 2차원 배열인 부분만 제외하면 N-Queen 문제와 거의 동일하다.

 

/*
 * 백트래킹 언제할수 있는지 일단 세로줄과 가로줄, 3x3에 같은게 있으면 백트래킹! 끝까지 도달하면 저장. 그리고 빈칸이 0일때, 끝
 */
public class BaekJoon_15_2580 {
	private static BufferedReader reader;
	private static BufferedWriter writer;
	private static int[][] sudoku;
	private static ArrayList<int[]> list; // 빈칸 저장소
	private static boolean check;

	private static void dfs(int count) throws IOException {
		if (count == list.size()) {
			print();
			check = true; // 가능한 판을 찾으면 더 이상 진행할 필요가 없다.
			return;
		}

		if (check) // 이미 가능한 판을 찾았으면 그만 dfs 진행
			return;

		for (int i = 1; i <= 9; i++) {
			int x = list.get(count)[0];
			int y = list.get(count)[1];
			if (isPossible(x, y, i)) {
				sudoku[x][y] = i;
				dfs(count + 1);
				/*
				 * 이미 위에서 가능한 케이스였다면 값 대입이 이루어졌을텐데, 그러면 결과를 찾고 출력까지 했을것이다. 근데 진행을하다가 맞는길이 아니라면
				 * 백트래킹으로 그만 검사하고 또다른 케이스를 검사해야할 텐데, 당연히 깔끔하게 새로운 판에서 검사를 진행해야한다. 그게아니라면 값을
				 * 초기화해서 새로운 판을 만들어야한다.
				 */
				sudoku[x][y] = 0; 
			}
		}

	}

	private static boolean isPossible(int x, int y, int prev) {
		// 열 검사
		for (int i = 0; i < 9; i++) {
			if (sudoku[x][i] == prev)
				return false;
		}

		// 행 검사
		for (int i = 0; i < 9; i++) {
			if (sudoku[i][y] == prev)
				return false;
		}

		// 3x3 검사 만약 (1,4)면 두번째 칸
		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 (sudoku[i][j] == prev)
					return false;
			}
		}

		// 다 통과되면 true
		return true;
	}

	private static void print() throws IOException {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				sb.append(sudoku[i][j]).append(" ");
			}
			sb.append("\n");
		}
		writer.write(sb.toString());
	}

	public static void main(String[] args) throws IOException {
		reader = new BufferedReader(new InputStreamReader(System.in));
		writer = new BufferedWriter(new OutputStreamWriter(System.out));
		sudoku = new int[9][9];
		list = new ArrayList<int[]>();

		StringTokenizer st;
		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < 9; j++) {
				sudoku[i][j] = Integer.parseInt(st.nextToken());
				if (sudoku[i][j] == 0)
					list.add(new int[] { i, j });
			}
		}

		dfs(0);

		reader.close();
		writer.flush();
		writer.close();
	}

}

 

여기서 좀 중요하게 생각해야하는 부분은 ..

 

if (isPossible(x, y, i)) {
	sudoku[x][y] = i;
	dfs(count + 1);
	sudoku[x][y] = 0; 
}

요부분이다. 왜 dfs 종료후에 0을 다시 대입하는가? 백준 문제에 등재되어 있는 문제의 예제는 이 0을 대입하는 코드가 존재하지 않아도 작동하는 그 이유는 한번의 케이스만에 정답을 찾았기 때문이다. 하지만 그런 경우는 거의 없을 것이다. dfs가 종료되었는데 뒤로 돌아온다는 건 원하는 케이스를 찾지 못했기 때문에 처음부터 다른 케이스를 찾아봐야한다는 의미로 보면 된다. 처음부터 다시 판별해야 하기 때문에 입력으로 주어졌던 처음의 판을 가지고 케이스를 다시 판별해야 하기 때문에 0을 넣어서 처음의 판으로 되돌려준 것이다.

 

 

 

대충넘어가지말자.