[G5] 백준 3967번 매직 스타 C++ 구현, 백트래킹

리뷰

 

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

어우... 구현 빡샜다. 마지막엔 알수 없는 버그같은게 있어서 고생좀했다.

 

 

전역 변수

• Pos : 위치 정보를 정의할 구조체
• xp : 매직이 들어가는 좌표를 저장할 Pos타입 배열
• v : 이미 매직이 들어가 있는 상태를 체크할 배열
• u : 이미 사용한 정수를 체크할 배열
• c : 현재 라인에 존재하는 정수 개수를 저장할 배열
• s : 현재 라인의 정수 합을 저장할 배열
• Group : 현재 위치가 속한 라인 번호를 정의할 구조체
• g : 매직 좌표 별 속한 라인 번호를 저장할 Group타입 배열
• m : 매직스타 맵 정보를 저장할 2차원 배열
• flag : 최적해를 찾았는지 여부를 체크할 변수
• memo : 초기에 채워져있던 매직의 위치와 문자를 저장할 pair<Pos, char>>타입 벡터

 

함수

1. chk

bool chk(const Group& group) {
	if (c[group.g1] == 4 && s[group.g1] != 26) return false;
	if (c[group.g2] == 4 && s[group.g2] != 26) return false;
	return true;
}

 

모든 라인이 조건에 부합하는지 여부를 체크할 함수

 

2. print

void print() {
	for (const auto& data : memo) {
		m[data.first.x][data.first.y] = data.second;
	}

	for (int i = 1; i < 6; ++i) {
		for (int j = 1; j < 10; ++j) {
			cout << m[i][j];
		}
		cout << "\n";
	}
}

 

매직 스타 맵 정보를 출력하기 위한 함수

 

3. bt

void bt(int level) {
	//print();
	if (flag) return;
	if (level == 13) {
		print();
		flag = true;
		return;
	}
	if (v[level]) bt(level + 1);
	//cout << level << "\n";

	const Group& group = g[level];
	const Pos& pos = xp[level];
	int x = pos.x, y = pos.y;

	for (int i = 1; i < 13; ++i) {
		if (u[i]) continue;

		u[i] = true;
		++c[group.g1];
		s[group.g1] += i;
		++c[group.g2];
		s[group.g2] += i;
		m[x][y] = 'A' + i - 1;

		if (chk(group))bt(level + 1);

		u[i] = false;
		--c[group.g1];
		s[group.g1] -= i;
		--c[group.g2];
		s[group.g2] -= i;
		m[x][y] = 'x';
	}
}

 

매직스타에 사용할 수 있는 수를 대입하기 위한 함수

 

 

문제풀이

1. 맵 정보를 입력받아 m배열을 초기화한다.
2. 매직이 들어올 위치를 순회하며 이미 각인되어 있는 매직에 대해 v, u, c, s, memo배열을 초기화한다.
3. bt함수에 1을 매개변수로 전달하여 호출한다, 함수 내부에서 변수 level에 해당 값을 전달받는다.
4. 첫 번째 기저 조건으로 flag가 true인 경우 이미 최적해를 찾은 경우이므로 리턴처리한다.
5. 두 번째 기저 조건으로 level이 13에 도달한 경우 print함수를 호출하고 flag를 true로 변경한다. 이후 리턴처리한다.
6. 세 번째 기저 조건으로 v[level]이 true인 경우 이미 매직이 각인된 상태이므로 재귀단계를 올려 호출한다.
7. 변수 group, pos에 현재 매직의 그룹과 위치를 저장하고, 변수 x, y에 위치 정보를 파싱한다.
8. 1~12 중 사용할 수 있는 정수가 있을 경우 방문처리한다.
9. c, s에 현재 매직이 속한 그룹의 수치를 증가, m배열에 알맞은 문자를 배정한다.
10. chk함수에 group을 매개변수로 전달하여 호출하고, 반환값이 true인 경우 재귀 단계를 높여 bt함수를 호출한다.
11. 재귀가 종료된 후엔 변경값을 원상복구한다.
12. flag가 true가 될때까지 위 로직을 반복 수행한다.

 

트러블 슈팅

1. v가 true인 경우 해당 매직을 사용하지 않게 구현했는데 자꾸 출력 시 x로 바뀌는 버그가 발생했다.
2. 원인을 디버깅하기엔 너무 범위가 광범위하여 메모해놓고 출력 시점에 값을 덮어 씌워주어 해결했다.

 

참고 사항

1. 매 라인이 완성될 때마다 현재 라인이 유효한지 체크 후 가능한 경우만 재귀를 수행해 재귀 호출 범위를 줄였다.
2. 1-based-indexing을 사용할 경우 하드코딩된 값을 사용한 xp, g등의 배열은 인덱스에 유의해야한다.

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;

struct Pos {
	int x, y;
};
Pos xp[13] = {
	{},
	{1, 5},
	{2, 2}, {2, 4}, {2, 6}, {2, 8},
	{3, 3}, {3, 7},
	{4, 2}, {4, 4}, {4, 6}, {4, 8},
	{5, 5}
};
bool v[13], u[13];
int c[7], s[7];
struct Group {
	int g1, g2;
};
Group g[13] = {
	{},
	{1, 3},
	{4, 6}, {1, 6}, {3, 6}, {5, 6},
	{1, 4}, {3, 5}, 
	{1, 2}, {2, 4}, {2, 5}, {2, 3},
	{4, 5}
};
char m[6][10];
bool flag;
vector<pair<Pos, char>> memo;

bool chk(const Group& group) {
	if (c[group.g1] == 4 && s[group.g1] != 26) return false;
	if (c[group.g2] == 4 && s[group.g2] != 26) return false;
	return true;
}

void print() {
	for (const auto& data : memo) {
		m[data.first.x][data.first.y] = data.second;
	}

	for (int i = 1; i < 6; ++i) {
		for (int j = 1; j < 10; ++j) {
			cout << m[i][j];
		}
		cout << "\n";
	}
}

void bt(int level) {
	//print();
	if (flag) return;
	if (level == 13) {
		print();
		flag = true;
		return;
	}
	if (v[level]) bt(level + 1);
	//cout << level << "\n";

	const Group& group = g[level];
	const Pos& pos = xp[level];
	int x = pos.x, y = pos.y;

	for (int i = 1; i < 13; ++i) {
		if (u[i]) continue;

		u[i] = true;
		++c[group.g1];
		s[group.g1] += i;
		++c[group.g2];
		s[group.g2] += i;
		m[x][y] = 'A' + i - 1;

		if (chk(group))bt(level + 1);

		u[i] = false;
		--c[group.g1];
		s[group.g1] -= i;
		--c[group.g2];
		s[group.g2] -= i;
		m[x][y] = 'x';
	}
}

int main() {
	for (int i = 1; i < 6; ++i) {
		for (int j = 1; j < 10; ++j) {
			cin >> m[i][j];
		}
	}
	
	for (int i = 1; i < 13; ++i) {
		const Group& group = g[i];
		const Pos& pos = xp[i];
		int x = pos.x, y = pos.y;
		if (m[x][y] == 'x') continue;

		//cout << m[x][y] << "\n";
		int val = m[x][y] - 'A' + 1;
		v[i] = true;
		u[val] = true;

		++c[group.g1];
		s[group.g1] += val;
		++c[group.g2];
		s[group.g2] += val;
		
		memo.push_back({ xp[i], m[x][y] });
	}
	
	//for (int i = 1; i < 13; ++i) cout << i << " : " << v[i] << "\n";
	bt(1);
}