[백준] 매직 스타

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

3967번: 매직 스타

dfs를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면,

1부터 12의 숫자가 각 줄의 합이 26이 되도록 올바르게 배정될 수 있도록 배정하여, 가장 사전순으로 빠른 경우를 출력해야 하는 것이 문제입니다.

 

<Solution>

DFS를 이용하면 됩니다. 계속 모양을 순회하지 않도록 미리, 12개의 점의 좌표를 기록해두는 방식을 이용합니다.

 

추가적으로 가지치기를 위해, 각 줄에 0~5의 번호를 매겨서 각 줄에 사용된 원소의 수와, 현재까지의 합을 기록해나가면서 진행합니다.

 

실제 구현은 아래와 같습니다.

 

#include <iostream>
using namespace std;
char map[5][10];

int r[] = {0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4};
int c[] = {4, 1, 3, 5, 7, 2, 6, 1, 3, 5, 7, 4};

int s[6];
int s_cnt[6];

// 각각이 두개에 속함
int g[2][12] = {{0, 3, 0, 2, 3, 0, 2, 0, 4, 5, 1, 4},
				{2, 4, 3, 3, 5, 4, 5, 1, 1, 1, 2, 5}};

int used[12];

int empty_[12];

int cnt_empty;

void InputData(){
	for (int h=0; h<5; h++){
		cin >> map[h];
	}
}
void OutputData(){
	for (int h=0; h<5; h++){
		cout << map[h] << endl;
	}
}

bool dfs(int k){ // 지금까지 몇개 추가했는지

	if(k>= cnt_empty) return true;

	// 추가해야 하는 위치
	int to_append_r = r[empty_[k]];
	int to_append_c = c[empty_[k]];
	// 해당하는 위치가 속한 group
	int group1 = g[0][empty_[k]];
	int group2 = g[1][empty_[k]];

	for(int i = 0 ;i<12; i++){
		if(used[i]) continue;

		// 사용중이 아니라면 
		// 추가 가능할때 추가함

		// 불가능한 경우들
		if(s_cnt[group1]+1 == 4){ // 4개 더했는데 26이 아닌경우
			if(s[group1]+i+1 != 26) continue;
		}
		else{ // 4개 보다 덜더했는데 26이미 넘거나 같음
			if(s[group1]+i+1 >= 26) continue;
		}

		//반대방향도 마찬가지
		if(s_cnt[group2]+1 == 4){ // 4개 더했는데 26이 아닌경우
			if(s[group2]+i+1 != 26) continue;
		}
		else{ // 4개 보다 덜더했는데 26이미 넘거나 같음
			if(s[group2]+i+1 >= 26) continue;
		}

		used[i] = 1;

		s[group1] +=i+1; s_cnt[group1]++;
		s[group2] += i+1; s_cnt[group2]++;
		
		// map 에 마킹
		map[to_append_r][to_append_c] = 'A' + i;

		if(dfs(k+1)){
			return true;
		}
		//원상복구
		
		used[i] = 0;
		s[group1] -=i+1; s_cnt[group1] --;
		s[group2] -= i+1; s_cnt[group2]--;
	}
	return false;
}

void solution(){
	for(int i = 0; i<12 ;i++){
		int r_ = r[i], c_ = c[i];
		if(map[r_][c_] == 'x'){
			empty_[cnt_empty++] = i;
		}
		else{
			s[g[0][i]] += map[r_][c_] - 'A' + 1;
			s[g[1][i]] += map[r_][c_] - 'A' + 1;
			s_cnt[g[0][i]] +=1;
			s_cnt[g[1][i]] +=1;

			used[map[r_][c_] - 'A'] = 1;
		}
	}

	dfs(0);

}

int main(){
	InputData();

	solution();

	OutputData();
	return 0;
}