[G4] 백준 2239번 스도쿠 C++ 백트래킹, 구현

리뷰

 

문제를 제대로 읽지 않아 대각선까지 일치해야 하는줄 알았다.

처음엔 해쉬 + Find를 통해 풀어야 하나 고민했는데 깊게 생각하지 않고 열, 행, 그룹으로 방문처리 하며 재귀를 사용하면 된다. 너무 어렵게 생각하지 말자

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

 

문제 풀이

전역 변수

• lst : 맵 정보를 나타낼 정수형 2차 배열
• cnt : 맵에 남아있는 0의 개수를 체크할 변수
• flag : 스도쿠 퍼즐이 완성되었는지 체크할 변수
• cols : 현재 행 기준 모든 열의 방문처리를 체크할 정수형 2차 배열
• rows : 현재 열 기준 모든 행의 방문처리를 체크할 정수형 2차 배열
• groups : 3*3 크기의 그룹 내의 방문처리를 체크할 정수형 3차 배열

 

1. 9 * 9 크기의 for문을 개행해 준다 처음 9번에 나누어 문자열 s에 첫 행의 정보를 담아온다.
2. 해당 행의 9개의 문자를 '0'을 빼줌으로서 정수형으로 타입 변환을 해준 뒤 lst에 저장해 준다.
3. 저장된 값이 1이상일 경우 cols, rows, groups에 방문처리를 해준다, 아닐 경우 cnt의 개수를 늘려준다.
4. dfs를 통해 탐색을 시작해 준다, 매개변수로는 탐색을 시작할 row의 인덱스를 전달해 준다.
5. (9 - 현재 행의 개수) * 9 범위를 탐색하며 lst상에서 0인 값을 만난다면 1~9 값을 대입해 본다.
6. 만약 cols, rows, groups에 방문처리가 된 수라면 continue 처리해 준다.
7. 세 배열 모두 방문처리 되지 않은 수를 찾으면 방문처리 및 cnt의 개수를 줄여준 뒤 현재 위치를 해당 수로 교체한다.
8. 이후 현재 행을 기준으로 dfs를 한번 더 실행해 주며 재귀를 시작한다.
9. 재귀를 빠져나오면 방문처리를 풀어주고 현재 위치도 다시 0으로 만들어 준다.
10. 1 ~ 9번째 수를 모두 대입해 보았으면 return 처리를 해주면 된다.
11. 기저 조건으로는 cnt가 0이 되었을때 이다, 탐색을 1 ~ 9순으로 했으므로 자동으로 오름차순 정렬되어 있다. lst에 저장된 정보를 출력해 준 뒤 flag를 1로 설정하고 리턴 처리해 준다.
12. flag가 1일 경우 모든 dfs를 중지해 주면 된다.

 

참고 사항

대각선까지 방문처리는 고려하지 않아도 된다.

0인 값을 찾아서 값 대입을 마쳤다면 바로 return 처리해 주는 부분이 가지치기가 된다.

for문을 돌릴 범위를 col로 전해주는 것도 미미하지만 시간을 줄이는 데에 효과가 있다.

 

 

정답 코드

#include<iostream>

using namespace std;

int lst[9][9], cnt = 0, flag = 0;
int cols[9][10] = { 0, };
int rows[9][10] = { 0, };
int groups[3][3][10] = { 0, };

void dfs(int col) {
	if (flag) return;
	if (!cnt) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << lst[i][j];
			}
			cout << "\n";
		}
		flag = 1;
		return;
	}
	for (int i = col; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (!lst[i][j]) {
				for (int k = 1; k <= 9; k++) {
					if (cols[i][k]) continue;
					if (rows[j][k]) continue;
					if (groups[i / 3][j / 3][k]) continue;
					cols[i][k] = 1;
					rows[j][k] = 1;
					groups[i / 3][j / 3][k] = 1;
					cnt--;
					lst[i][j] = k;
					dfs(i);
					lst[i][j] = 0;
					cnt++;
					cols[i][k] = 0;
					rows[j][k] = 0;
					groups[i / 3][j / 3][k] = 0;
				}
				return;
			}
		}
	}
}

int main() {
	for (int i = 0; i < 9; i++) {
		string s; cin >> s;
		for (int j = 0; j < 9; j++) {
			lst[i][j] = s[j] - '0';
			if (lst[i][j]) {
				cols[i][lst[i][j]] = 1;
				rows[j][lst[i][j]] = 1;
				groups[i / 3][j / 3][lst[i][j]] = 1;
			}
			else cnt++;
		}
	}
	dfs(0);
}