[백준 C++] 1343. 폴리오미노

문제 링크

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

예제 입력 / 출력

// 예제 입력 1
XXXXXX

// 예제 출력 1
AAAABB

// 예제 입력 2
XX.XX

// 예제 출력 2
BB.BB

// 예제 입력 3
XXXX....XXX.....XX

// 예제 출력 3
-1

// 예제 입력 4
X

// 예제 출력 4
-1

// 예제 입력 5
XX.XXXXXXXXXX..XXXXXXXX...XXXXXX

// 예제 출력 5
BB.AAAAAAAABB..AAAAAAAA...AAAABB

풀이

📍 알고리즘

• board를 자리 순서대로 탐색하면서 '.' 문자가 나오는 경우 만약 앞의 문자가 홀수 개수로 끝났을 경우는 덮을 수 없는 경우이므로 -1을 반환, 'X' 문자가 나오는 경우는 2개일 때 4개일 때를 구분해서 각각 "AAAA", "BB"로 출력되게 해준다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(void) {

	string board, result;
	int cnt = 0;

	cin >> board;

	board += ' ';

	for (int i = 0; i < board.size() - 1; i++) {

		if (board[i] == 'X') cnt++;

		if (board[i] == '.') {
			result += ".";
			if (cnt % 2 != 0) break;
			else cnt = 0;
		}

		if (cnt == 2 && board[i + 1] != 'X') {
			result += "BB";
			cnt = 0;
		}
		else if (cnt == 4) {
			result += "AAAA";
			cnt = 0;
		}


	}

	if (cnt % 2 == 1) cout << -1;
	else cout << result;

}