[BOJ 3283 // C++] BARCODE

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 3283번 문제인 BARCODE이다.
문제는 아래 링크를 확인하자.

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

3283번: BARCODE

고려해야 할 케이스가 많은 DP문제이다.

 

먼저 주어진 입력을 잘 처리하여 각 세로줄이 검은 줄('B'로 표기), 하얀 줄('W'로 표기), 모르는 줄('?'로 표기) 중 무엇인지를 구해두자. 이 과정에서 한 세로줄에 'B'와 'W'와 같이 있는 경우가 발견된다면 "UNDETERMINABLE"을 출력해주자.

 

그 뒤, 초기값으로 앞의 두 세로줄이 의미할 수 있는 문자열에 대한 상태를 저장하고, 세번째 세로줄부터 각 세로줄이 해당세로줄을 포함하는 크기 1 또는 2의 문자열로 구간을 나눌 수 있는지의 여부에 따라 DP를 진행해 문제를 해결해주자.

 

아래의 구현에서의 dp배열의 값은 "여러 경우가 존재함"을 의미하는 -1, "경우가 존재하지 않음"을 의미하는 0, "해당 세로줄이 그 한칸으로 기능하는 경우가 가능한 유일한 해석임"을 의미하는 1, "해당 세로줄이 그 전 세로줄과 이어 한칸으로 기능하는 경우가 가능한 유일한 해석임"을 의미하는 2로 구성되어있으니 코드를 읽을 때 참고하자. 여기에서 배열의 값인 1과 2는 dp의 해를 역추적하는 데에도 유용하게 사용할 수 있다. 

 

예외적으로, '?'를 의미하는 세로줄 하나만이 입력이 들어왔을 경우의 답은 "0"임에 유의하자. '?'를 'B'로 해석해도 'W'로 해석해도 해당 문자열은 항상 "0"으로 동일하게 해석되기 때문이다. 이와 같이 복수의 해석이 가능하지만 그 모든 해석이 같은 문자열을 가리키는 경우는 이 경우가 유일하다. (증명은 간단하므로 생략한다.)

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N;
string s[5];
bool chk = 1;
char arr[100];
int dp[100][2];
int cnt;

int idx, c;
vector<int> ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int r = 0; r < 5; r++) cin >> s[r];

	for (int i = 0; i < N; i++) {
		bool black = 0, white = 0;
		for (int r = 0; r < 5; r++) {
			if (s[r][i] == '.') white = 1;
			else if (s[r][i] == 'X') black = 1;
		}
		if (black && white) chk = 0;
		else if (black) arr[i] = 'B';
		else if (white) arr[i] = 'W';
		else arr[i] = '?';
	}

	if (!chk) {
		cout << "UNDETERMINABLE";
		return 0;
	}
	
	if (N == 1) {
		cout << '0';
		return 0;
	}

	if (arr[0] == 'B') dp[0][0] = 1;
	else if (arr[0] == 'W') dp[0][1] = 1;
	else dp[0][0] = dp[0][1] = 1;

	if (arr[0] == 'B' && arr[1] == 'B') dp[1][0] = 2;
	else if (arr[0] == 'B' && arr[1] == 'W') dp[1][1] = 1;
	else if (arr[0] == 'B' && arr[1] == '?') dp[1][0] = 2, dp[1][1] = 1;
	else if (arr[0] == 'W' && arr[1] == 'B') dp[1][0] = 1;
	else if (arr[0] == 'W' && arr[1] == 'W') dp[1][1] = 2;
	else if (arr[0] == 'W' && arr[1] == '?') dp[1][0] = 1, dp[1][1] = 2;
	else if (arr[0] == '?' && arr[1] == 'B') dp[1][0] = -1;
	else if (arr[0] == '?' && arr[1] == 'W') dp[1][1] = -1;
	else dp[1][0] = -1, dp[1][1] = -1;

	for (int i = 2; i < N; i++) {
		if (dp[i - 2][1] && (arr[i - 1] == 'B' || arr[i - 1] == '?') && (arr[i] == 'B' || arr[i] == '?')) {
			if (dp[i - 2][1] < 0 || dp[i][0]) dp[i][0] = -1;
			else dp[i][0] = 2;
		}
		if (dp[i - 2][0] && (arr[i - 1] == 'W' || arr[i - 1] == '?') && (arr[i] == 'W' || arr[i] == '?')) {
			if (dp[i - 2][0] < 0 || dp[i][1]) dp[i][1] = -1;
			else dp[i][1] = 2;
		}
		if (dp[i - 1][1] && (arr[i] == 'B' || arr[i] == '?')) {
			if (dp[i - 1][1] < 0 || dp[i][0]) dp[i][0] = -1;
			else dp[i][0] = 1;
		}
		if (dp[i - 1][0] && (arr[i] == 'W' || arr[i] == '?')) {
			if (dp[i - 1][0] < 0 || dp[i][1]) dp[i][1] = -1;
			else dp[i][1] = 1;
		}
	}
	
	if (dp[N - 1][0] == -1 || dp[N - 1][1] == -1 || (dp[N - 1][0] > 0 && dp[N - 1][1] > 0) || (dp[N - 1][0] == 0 && dp[N - 1][1] == 0)) {
		cout << "UNDETERMINABLE";
		return 0;
	}

	idx = N - 1;
	if (dp[idx][1] > 0) c = 1;

	while (idx > -1) {
		ans.emplace_back(dp[idx][c] - 1);
		idx -= dp[idx][c];
		c ^= 1;
	}

	while (!ans.empty()) {
		cout << ans.back();
		ans.pop_back();
	}
}