[백준] 3967번 - 매직 스타 / C++

문제

매직 스타는 1부터 12까지 숫자가 헥사그램(hexagram)에 채워져 있는 모양으로 이루어져 있다.

매직 스타의 이름에 매직이 들어가는 이유는 숫자 네 개로 이루어진 줄의 숫자를 모두 합하면 26이 되기 때문이다. 위의 그림의 여섯 줄에 쓰여 있는 숫자는 다음과 같다.

• 1 + 4 + 10 + 11
• 11 + 5 + 3 + 7
• 7 + 6 + 12 + 1
• 2 + 10 + 5 + 9
• 9 + 3 + 6 + 8
• 8 + 12 + 4 + 2

매직 스타를 채우는 방법은 여러 가지가 있다. 일부만 채워진 매직 스타가 주어졌을 때, 수를 전부 다 채워서 매직 스타를 만드는 프로그램을 작성하시오.

 

입력

매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기 위해서 사용하는 문자이다. 모든 입력은 예제 입력과 같은 형태로 주어진다.

 

출력

매직 스타를 만들 수 있는 방법 중에 사전 순으로 가장 앞서는 방법을 출력한다. (모든 줄을 순서대로 붙여서 하나의 문자열로 만든 뒤, 사전 순으로 비교한다.) 항상 정답이 존재하는 경우만 입력으로 주어진다.

 

코드

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

#define N	5
#define M	9
#define MAGIC	26

using namespace std;

string star[N];
string magic_star[N];
string per;

// 사용되지 않은 알파벳으로 초기 순열을 구성함 (오름차순)
void make_per()
{
	bool check[12];
	int i, j;

	memset(check, false, sizeof(check));
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (star[i][j] == '.' || star[i][j] == 'x')
				continue;
			check[star[i][j] - 'A'] = true;
		}
	}
	for (i = 0; i < 12; i++)
	{
		if (!check[i])
			per += ('A' + i);
	}
}

// 순열에 따라 magic_star를 구성함
void fill_star()
{
	int i, j, idx = 0;

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (star[i][j] == 'x')
				magic_star[i][j] = per[idx++];
		}
	}
}

// 알파벳을 숫자로 바꿈
int convert(char c)
{
	return c - 'A' + 1;
}

// 매직 스타인지 확인함
bool is_magic()
{
	int i, j, r, c, sum;
	int sr[] = {1, 3, 0, 1, 0, 1};
	int sc[] = {1, 1, 4, 1, 4, 7};
	int dr[] = {0, 1, 1};
	int dc[] = {2, 1, -1};

	for (i = 0; i < 6; i++)
	{
		r = sr[i];
		c = sc[i];
		sum = 0;
		for (j = 0; j < 4; j++)
		{
			sum += convert(magic_star[r][c]);
			r += dr[i / 2];
			c += dc[i / 2];
		}
		if (sum != MAGIC)
			return false;
	}
	return true;
}

int main()
{
	int i;

	for (i = 0; i < N; i++)
	{
		cin >> star[i];
		magic_star[i] = star[i];
	}	
	make_per();
	do
	{
		fill_star();
		if (is_magic())
			break;
	} while (next_permutation(per.begin(), per.end()));
	for (i = 0; i < N; i++)
		cout << magic_star[i] << "\n";
	return 0;
}

 

결과가 여러 가지일 때 사전순으로사전 순으로 앞선 방법을 출력한다. 'A'~'L'의 알파벳이 모두 사용되어야 하므로 입력받은 모양에서 사용되지 않은 알파벳을 확인한다. 사전 순으로 앞선 방법부터 확인하기 위해 사용되지 않은 알파벳으로 구성된 오름차순의 문자열을 만든다. 이 문자열을 사용해 가능한 경우를 확인하여 매직 스타를 찾는다. 순열을 통해 사전 순으로 검사하기 때문에 매직 스타를 찾는다면 즉시 출력하고 종료한다.

 

링크

3967번: 매직 스타

inbdni/Baekjoon