2020-0819 "백준 2580번: 스도쿠"를 풀며

알고리즘 문제를 해결한다는건 정말 생각보다 쉽지 않은 일이다. 내가 선택한 방법이 완전히 틀린 방법이어서 처음부터 다시 시작해야 할 때도 있다. 알고리즘은 내가 예상했던것 보다 수학적 사고력을 많이 요하는 분야인것 같다.

수학적 사고력이란 뭘까? 어릴적에는 단순히 재능이라고 생각했다. 수능 문제를 30분만에 두번이나 풀고 자는 친구들을 보면서 많이 좌절했던것 같다. 그치만 지금은 수학적 사고력이란 체력과 인내심, 그리고 나에 대한 관용이라고 생각한다. 솔직히 어릴적에는 나는 안된다는 생각에 사로잡혀있기도 했고, 문제가 안풀렸을때 그 좌절감을 견디지 못했다. 그래서 결국 풀이방법을 많이 외우다시피하면서 억지로 억지로 공부했었다. 

지금의 나는 드디어 내가 공부하고자 하는 분야를 만났고, 나의 전공을 정말 사랑하게 되었다. 옛날의 나와 사고방식도 많이 달라졌다. 그래서 물론 알고리즘을 공부하면서도 지금 어려움을 겪고 있지만, 지금은 옛날과 다르다고 생각한다. 지금은 공부를 할수 있도록 도와주는 환경도 있고, 옛날보다 시간도 좀더 여유롭다(실력을 올려야 하는). 가장 압박이 심한 부분이라고 하면 아무래도 피어프래셔겠지. 그래도 나는 나에게 주어진것에 대해 감사할줄 알아야 한다는것을 안다. 

지금의 고뇌와 시간들이 복리로 쌓여갈것을 나는 안다. 고민의 과정 그 자체가 나에게 필요한 공부라는 것을 안다. 사람을 많이 만나본 사람만이 사람보는 눈이 생기는것 처럼, 알고리즘도 용기를 가지고 많은 문제들에 도전해보고 문제를 보는 눈과 힘이 생겨야 한다는것을 안다. 결국, 알고리즘 공부는 겁이 많고 회피하고싶어하는 나를 어떻게 대하느냐의 문제일것 같다는 생각도 든다.

 

문제는 다음과 같다.

내가 처음으로 시도했던 방법은 정말 황당하게도 브루트포스였다. 만들었던 함수는 크게 세개였다 

• horCheck(): 가로열을 검사해서 없는 수를 리턴
• verCheck(): 세로열을 검사해서 없는 수를 리턴
• boxCheck(): 3x3을 검사해서 없는수를 리턴

여기에 스도쿠가 꽉찼는지 검사하는 함수, 입출력 함수를 만들었다. 

2중포문을 돌면서 0을 만나면 3가지 함수를 돌려서 내용을 채우는 식으로 코드를 짰다. 

#include <iostream>
#include <vector>

using namespace std;

int map[9][9];
struct Node { int y, x; };
vector<Node> vect;

void init() {
	for (int y = 0; y < 9; y++) {
		for (int x = 0; x < 9; x++) {
			scanf("%d", &map[y][x]);
			if (map[y][x] == 0) {
				vect.push_back({ y, x });
			}
		}
	}
}

void showing() {
	for (int y = 0;y < 9; y++) {
		for (int x = 0; x < 9; x++) {
			printf("%d ", map[y][x]);
		}
		if( y != 8) printf("\n");
	}
}

bool isFull() {
	for (int y = 0; y < 9; y++) {
		for (int x = 0;x < 9; x++) {
			if (!map[y][x]) return false;
		}
	}
	return true;
}

int horCheck(int row) {

	int DAT[10] = { 0 };

	for (int i = 0; i < 9;i++) {
		DAT[map[row][i]]++;
	}

	if (DAT[0] > 1) return 0;
	else if(DAT[0] == 1){
		for (int i = 1; i <= 9; i++) {
			if (DAT[i] == 0) return i;
		}
	}
}

int verCheck(int col) {

	int DAT[10] = { 0 };

	for (int i = 0; i < 9;i++) {
		DAT[map[i][col]]++;
	}

	if (DAT[0] > 1) return 0;
	else if (DAT[0] == 1) {
		for (int i = 1; i <= 9; i++) {
			if (DAT[i] == 0) return i;
		}
	}
}

int boxCheck(int y, int x) {

	int DAT[10] = { 0 };
	int fy = (y / 3) * 3;
	int fx = (x / 3) * 3;

	for (int dy = fy; dy <= fy + 2; dy++) {
		for (int dx = fx; dx <= fx + 2; dx++) {
			DAT[map[dy][dx]]++;
		}
	}

	if (DAT[0] > 1) return 0;
	else if (DAT[0] == 1) {
		for (int i = 1; i <= 9; i++) {
			if (DAT[i] == 0) return i;
		}
	}
	
}

int main() {

	freopen("Text.txt", "r", stdin);

	init();
	int to = vect.size();

	while (to) {
		int cnt = 0;
		for (int i = 0; i < to; i++) {
			int re = 0;
			int y = vect[i].y;
			int x = vect[i].x;
			
			re = horCheck(y);
			if (re) {
				map[y][x] = re;
				vect.erase(vect.begin() + i);
				cnt++;
				break;
			}
			re = verCheck(x);
			if (re) {
				map[y][x] = re;
				vect.erase(vect.begin() + i);
				cnt++;
				break;
			}
			re = boxCheck(y, x);
			if (re) {
				map[y][x] = re;
				vect.erase(vect.begin() + i);
				cnt++;
				break;
			}
		}
		to--;
	}

	showing();

	return 0;
}

그런에 이건 문제의 기본 전제에 접근조차 못한 풀이었다. 이 문제는 DFS로 푸는 문제였기 때문이다. 정말 어이가 없다..

이 풀이는 완전히 틀린 풀이라는 것이다. 이 해결책을 구하는데 이틀이 걸렸건만..... 

 

지금은 DFS를 어떻게 이용해야 이 문제를 "정확성"면에서 풀수 있는지 고민중이다. 이에 대한 해결책이 생기면 다시 시도해보고 그다음은 최적화를 해야겠지. 물론 배운점도 많지만 쉽지 않다. 대학원 연구생들의 마음을 조금이나마 이해할수 있을것 같달까..... 지금의 노력들이 부디 헛되지 않기를 바란다.