[G4] 백준 2580번 스도쿠 C++ 백트래킹

리뷰

 

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

별 생각없이 접근하고 예제가 맞는 것을 확인하고 제출했다가 곧 바로 틀려버렸다.

초기 맵이 모두 0인 상태로 돌려보니 값이 이상한 것을 확인하고 좌표를 통해 접근했더니 AC를 받았다.

맵의 크기가 9 * 9라서 스택 오버플로우가 나올 것 같았지만 그정도 재귀로는 터지지 않나보다.

 

 

전역 변수

• lst : 초기 맵 정보를 저장하기 위한 정수형 2차원 배열
• vc : 열을 기준으로 방문 처리를 하기 위한 정수형 2차원 배열
• vr : 행을 기준으로 방문 처리를 하기 위한 정수형 2차원 배열
• vs : 3 * 3크기의 구역을 기준으로 방문 처리를 하기 위한 정수형 2차원 배열
• flag : 수도쿠가 완성 되었는지를 체크하기 위한 논리형 변수

 

함수

1. bt

void bt(int x, int y)

 

각 좌표의 맵 정보를 탐색하며 수도쿠를 완성시키기 위한 백트래킹 함수

1. 매개변수로 탐색을 진행할 x, y좌표를 전달받는다.
2. 첫번째 기저 조건으로 flag가 true인 상태라면 탐색을 중지하고 리턴해 준다.
3. 두번째 기저 조건으로 x, y가 각각 9, 0에 도달했다면 맵 상태를 출력하고 flag를 true로 만든 뒤 리턴한다.
4. 만약 맵 상에서 x, y좌표의 값이 0이 아니라면 좌표를 이동하여 재귀를 호출해 준다.
5. x, y좌표의 값이 0이라면 1 ~ 9 중 들어갈 수 있는 숫자를 하나씩 넣어가며 재귀를 호출해 준다.
6. 들어갈 수 있는 조건은 행, 열, 구역 내에 해당 숫자가 방문처리 되지 않았으며, flag가 flase일 때이다.
7. 조건을 만족하는 숫자가 있을 경우 방문처리 및 맵 상에서 숫자를 변경해 준 후 재귀를 호출해 주면 된다.
8. 재귀를 수행한 후에는 방문처리 및 맵 정보를 다시 0으로 만들어 주어야 한다.

 

문제풀이

1. 9 * 9번의 반복문을 통해 lst배열에 초기 맵 정보를 입력 받아준다.
2. 0이 아닌 값이 들어왔을 경우 vc, vr, vs배열에 각 열, 행, 구역에 입력받은 숫자에 대하여 방문처리를 진행한다.
3. 입력을 모두 받은 후 bt함수에 초기 좌표 0, 0을 전달하여 백트래킹을 시작한다.
4. 백트래킹의 기저조건에 도달했을 경우 당시 맵 정보를 출력하고 재귀를 빠져나와 준다.

 

트러블 슈팅

1. 백트래킹 내에서 매번 for문을 통해 좌표를 탐색해 주었더니 바로 틀려서 좌표 탐색으로 변경해 주었다.
2. Visual Studio에서 AC를 받은 코드여도 잘못된 데이터를 읽는 중이라는 경고가 계속 출력되었다.
3. x가 배열의 범위를 넘어설 수 있다는 경고성 문구인듯 하다. 기저 조건에 따라 문제될 일은 없다.

 

참고 사항

• 3 * 3섹션을 나눌 때 행을 3으로 나눈 몫 * 3 + 열을 3으로 나눈 몫으로 총 9구역으로 나눌 수 있다.

 

정답 코드

#include<iostream>
using namespace std;

int lst[9][9];
bool vc[9][10];
bool vr[9][10];
bool vs[9][10];
bool flag;

void bt(int x, int y) {
	if (flag) return;
	if (x == 9 && y == 0) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
				cout << lst[i][j] << " ";
			}
			cout << "\n";
		}
		flag = 1;
		return;
	}

	if (lst[x][y]) {
		if (y < 8) bt(x, y + 1);
		else bt(x + 1, 0);
	}
	else {
		for (int i = 1; i < 10; ++i) {
			int area = 3 * (x / 3) + (y / 3);
			if (vc[x][i] || vr[y][i] || vs[area][i]) continue;
			if (flag) break;
			vc[x][i] = 1;
			vr[y][i] = 1;
			vs[area][i] = 1;
			lst[x][y] = i;
			if (y < 8) bt(x, y + 1);
			else bt(x + 1, 0);
			vc[x][i] = 0;
			vr[y][i] = 0;
			vs[area][i] = 0;
			lst[x][y] = 0;
		}
	}
}

int main() {
	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			cin >> lst[i][j];
			if (lst[i][j]) {
				int area = 3 * (i / 3) + (j / 3);
				vc[i][lst[i][j]] = 1;
				vr[j][lst[i][j]] = 1;
				vs[area][lst[i][j]] = 1;
			}
		}
	}
	bt(0, 0);
}