BOJ 24912 - 카드 색칠

문제 링크

문제#

영우는 나코더 신입생들을 환영하기 위해 정성스럽게 입부 환영 카드를 만들었다. 입부 환영 카드에서 소환된 기장 동현이의 환영이 신입생들을 환영할 것이다. 부기장인 이환이는 환영 카드의 색칠을 맡았다. 이환이는 각 카드를 일렬로 줄지어 놓고 빨간색, 초록색, 파란색 중 하나의 색으로 칠하려 한다. 그런데 그중 몇 개의 카드는 영우가 이미 색칠했다. 색칠은 다음 규칙에 따라야 한다.

• 단조로움을 피하기 위해, 인접한 카드는 서로 다른 색으로 칠해야 한다.

• 이미 색칠된 카드에 덧칠할 수 없다.

• 카드의 순서를 바꿀 수 없다.

하지만 이환이는 서울과학고등학교 동아리 '싸이컴'의 상훈이와 테트리스 대결을 해야 하기 때문에 환영 카드를 색칠할 시간 따위는 없다. 그러니까 신입생 환영 카드의 색칠은 여러분이 직접 하도록 하자.

입력#

첫째 줄에 카드의 개수를 나타내는 정수 $N$이 주어진다. 둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어진다. $i$번째 정수 $a_i$는 $i$번째 카드의 색깔을 나타낸다. 1, 2, 3은 각각 빨간색, 초록색, 파란색을 의미하며, 0은 $i$번째 카드가 색칠되어 있지 않음을 의미한다.

출력#

유일한 줄에 $N$개의 정수를 공백으로 구분하여 출력한다. 각 정수는 1, 2, 3 중 하나여야 하며, 주어진 조건에 맞아야 한다. 가능한 방법이 여러 가지인 경우, 그중 아무거나 출력한다. 만약 모든 조건에 맞는 색칠이 불가능하다면, 유일한 줄에 -1만 출력한다.

풀이#

이미 칠해진 인접 카드가 같은 색이면 어떤 방법으로도 조건을 만족할 수 없으므로 바로 -1을 출력한다. 그 외에는 비어 있는 카드마다 양옆과 다른 색을 하나 골라 채우면 된다.

색이 1, 2, 3 세 가지뿐이라서 현재 위치의 왼쪽과 오른쪽 색을 제외해도 적어도 하나의 후보가 남는다. 코드에서는 arr[i] == 0인 위치에서 arr[i - 1]과 arr[i + 1]을 체크한 뒤, 쓰이지 않은 색을 앞에서부터 선택한다.

왼쪽부터 차례대로 채우기 때문에 앞쪽 결정이 뒤로 전달된다. 오른쪽이 아직 0이면 금지색으로 작동하지 않으므로, 현재 선택만 이웃과 다르게 맞추면 다음 위치에서 다시 같은 방식으로 처리할 수 있다.

코드#

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
 
int n;
int arr[1000002];
 
void solve() {
	for (int i = 1; i <= n; i++) {
		if (arr[i] == 0) {
			bool color[4] = {0, 0, 0, 0};
			color[arr[i - 1]] = true;
			color[arr[i + 1]] = true;
 
			for (int j = 1; j <= 3; j++) {
				if (!color[j]) {
					arr[i] = j;
					break;
				}
			}
		}
	}
 
	for (int i = 1; i <= n; i++)
		cout << arr[i] << " ";
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		if (arr[i] != 0 && arr[i - 1] == arr[i]) {
			cout << -1 << '\n';
			return 0;
		}
	}
		
	solve();
	return 0;
}

복잡도#

• 시간 복잡도: 카드를 한 번 훑으므로 $O(N)$이다.
• 공간 복잡도: 색 배열로 $O(N)$을 사용한다.

마무리#

색이 세 가지라 양옆만 피하면 항상 남는 색이 있다. 불가능한 경우는 이미 칠해진 같은 색 이웃이 만든다.