[백준 3967] 매직 스타 (C++)

문제 링크: https://www.acmicpc.net/problem/3967

3967번: 매직 스타

1. 주의할 점

- 마지막에 모든 경로의 합을 구하면 TLE 발생한다. 특정 지점마다 검사해줘야 한다

 

2. 구현

- Check[] 배열을 전부 -1로 초기화한다

- Check[] 배열을 통해 해당 번호가 현재 사용중이라고 표시한다

- Test[][] 배열을 통해 어떤 경로에 위치한 숫자를 계산해야 하는지 표시한다

- DFS()를 수행하며 Idx가 5,8,11,12일때 특정 경로의 합을 구한다. 4,7,10,11일때 검사를 하지 않는 이유는, 해당 숫자에 이미 숫자가 할당되어 입력되었다면 검사를 안하고 넘어갈 수 있기 때문이다.

- For문을 통해 작은 숫자부터 들어갈 수 있는지 확인한다. 최초 경로 전부의 합이 22인 순간, 가장 사전순으로 앞에 위치한 경우를 만족하기 때문이다.

 

#include <iostream>
#include <string>
using namespace std;
struct info {
	int x, y;
};
info tmp;
char arr[5][9];
bool check[12] = { false, };
bool finish = false;
int num[12];
int test[6][4] = {
	{0,2,5,7},
	{0,3,6,10},
	{7,8,9,10},
	{1,2,3,4},
	{1,5,8,11},
	{4,6,9,11}
};

void dfs(int idx) {
	if (finish) return;
	if (idx == 12) {
		int t = 0;
		for (int j = 0; j < 4; j++)
			t += num[test[4][j]];
		if (t != 22)	return;
		t = 0;
		for (int j = 0; j < 4; j++)
			t += num[test[5][j]];
		if (t != 22)	return;
		int cnt = 0;
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 9; j++) {
				if (arr[i][j] != '.') {
					char c = num[cnt++] + 'A';
					cout << c;
				}
				else
					cout << arr[i][j];
			}
			cout << '\n';
		}
		finish = true;
		return;
	}
	if (idx == 5) {
		int t = 0;
		for (int j = 0; j < 4; j++)
			t += num[test[3][j]];
		if (t != 22) return;
	}
	else if (idx == 8) {
		int t = 0;
		for (int j = 0; j < 4; j++)
			t += num[test[0][j]];
		if (t != 22) return;
	}
	else if (idx == 11) {
		int t = 0;
		for (int j = 0; j < 4; j++)
			t += num[test[2][j]];
		if (t != 22) return;
		t = 0;
		for (int j = 0; j < 4; j++)
			t += num[test[1][j]];
		if (t != 22) return;
	}
	if (num[idx] != -1) dfs(idx + 1);		//이미 번호가 있는 경우
	else {
		for (int i = 0; i < 12; i++) {
			if (check[i]) continue;
			check[i] = true;
			num[idx] = i;
			dfs(idx + 1);
			num[idx] = -1;
			check[i] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int cnt = 0;
	for (int i = 0; i < 12; i++)	num[i] = -1;
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];
			char c = arr[i][j];
			if (c != '.') {
				if (c == 'x') cnt++;
				else {
					check[c - 'A'] = true;
					num[cnt++] = c - 'A';
				}
			}
		}
	dfs(0);
	return 0;
}