[C++] 백준 1314번: 폴리오미노

문제 링크

1314번: 폴리오미노

문제 요약

'.'와 'X'로 이루어진 보드판이 주어졌을 때, 'AAAA'와 'BB' 두 개의 폴리오미노를 이용해서 'X'를 모두 덮어야 한다.

접근 방법

상당히 쉬운 문제였습니다.
사전순으로 가장 앞서는 답을 출력해야 하는데, 알파벳 순으로 BB보다 앞에 있는 AAAA 폴리오미노를 보드판의 앞에서부터 검사하면서 채워줍니다. 끝까지 검사를 완료한 다음에는 BB 폴리오미노를 채워주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

void func(string& str, int sz, char c)
{
	for (int i = 0; i < str.size() - sz + 1; i++)
	{
		int cnt = 0;
		for (int j = i; j < i + sz; j++)
			if (str[j] == 'X')
				cnt++;

		if (cnt == sz)
		{
			for (int j = i; j < i + sz; j++)
				str[j] = c;
			i += (sz - 1);
		}
	}
}

int main(void)
{
	string str;
	cin >> str;

	if(str.size() >= 4)
		func(str, 4, 'A');
	if(str.size() >= 2)
		func(str, 2, 'B');

	for (auto& i : str)
		if (i == 'X')
			cout << -1 << '\n', exit(0);
	
	cout << str << '\n';
	return 0;
}