[백준 17359] 전구 길만 걷자 (C++)

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

문제

---

선린 친구들은 ✨인기스타 슈퍼인싸 예원쌤✨을 존경한다. 방학 동안 선생님을 뵐 수 없다니! 그래서 학생들은 방학식 날 💡전구 길만 걷자💡라는 엄청난 이벤트를 준비했다.

💡💡💡💡👨‍🏫💡💡💡💡

아무도 몰랐지만, 사실 선린의 과학실에는 전구가 일렬로 이어진 전구 묶음이 N개 있다. 학생들은 이 묶음을 일렬로 이어 전구 길을 만들기로 했다. 하지만 묶음에는 불이 들어오지 않는 전구가 섞여 있었는데, 전구들을 일렬로 이어 놓으니 켜진 전구와 꺼진 전구가 번갈아 나타나서 전구 길이 예쁘지 않았다.

그래서 학생들은 전구 길이 최대한 예쁘도록 묶음을 배열하려고 한다. 전구 길은 전구 상태가 바뀌는 횟수가 최소일 때 가장 예쁘다고 한다. 이는 켜진 전구를 1, 꺼진 전구를 0이라 했을 때, 전구 길에 01 또는 10이 최소로 나타나야 한다는 의미이다.

예를 들어, (1011) 묶음과 (1000) 묶음을 이어 붙여야 한다고 하자. 이때는 (10111000) 순서로 잇는 것이 (10001011) 순서로 잇는 것보다 예쁘다. 전자는 전구의 상태가 3번 바뀌고, 후자는 전구의 상태가 4번 바뀌기 때문이다.

그런데 갑자기 세한이가 코드를 작성해서 이를 계산하자고 한다.

세한이와 함께 전구 길을 예쁘게 꾸며보자!

 

입력

---

첫째 줄에 전구 묶음의 개수 N이 주어진다. (1 ≤ N ≤ 10)

둘째 줄부터 N개의 줄에 걸쳐, 각 줄마다 전구 묶음의 상태를 나타내는 문자열이 주어진다. 문자열은 0 또는 1로만 이루어져 있으며 0은 꺼진 전구를, 1은 켜진 전구를 의미한다.

문자열의 길이는 1 이상 100 이하이다.

 

출력

---

전구 묶음을 가장 예쁘게 배치했을 때, 전구의 상태가 바뀌는 횟수를 출력한다.

 

문제 풀이

---

백트래킹 문제.

전구 묶음끼리의 순서와 상관없이 하나의 전구 묶음에 전구의 상태가 바뀌는 부분이 있다면 적어도 그 부분의 횟수만큼은 전구의 상태가 바뀐다.

예를 들어 예시 1의 11100, 0000101, 011100의 볼드 처리된 부분은 세 전구 묶음의 순서와 상관없이 전구의 상태가 바뀐다. 따라서 정답 중 나올 수 있는 가장 작은 값은 6임을 알 수 있고, 이제 전구 묶음 순서에 따라 여기서 더 추가될 수 있다. 다시 말해 이번에 배치한 전구의 첫번째 전구의 상태와, 바로 전에 배치한 전구의 마지막 전구의 상태가 같지 않다면 count를 증가시켜주면 되는 것이다.

백트래킹을 통해 전구 순서를 모두 찾는다. N개의 전구묶음의 배치를 구한 후 배치한 전구 묶음이 이어지는 부분을 확인한다면 시간 초과가 발생하므로, 전구의 상태가 바뀌는 횟수를 백트래킹 함수의 인자로 넣는다. 이번에 사용할 전구 묶음을 선택한 후 전에 배치한 전구의 마지막 전구의 상태와 같은지 확인한 후, 다르다면 백트래킹 함수를 호출할 때 횟수 인자에 +1 해주면 된다.

 

아래는 코드.

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

int* index;
bool* isVisited;
string* str;
int N;
int answer = 100000;
int middles = 0;

void backTracking(int depth, int currentCount)
{
	if (depth == N)
	{
		answer = min(answer, currentCount);
	}
	else
	{
		for (int i = 0; i < N; i++)
		{
			if (isVisited[i] == false)
			{
				index[depth] = i;
				isVisited[i] = true;
				if (depth == 0)
				{
					backTracking(depth + 1, currentCount);
				}
				else
				{
					string prevString = str[index[depth - 1]];
					int length = prevString.length();
					if (prevString[length - 1] != str[index[depth]].at(0))
					{
						backTracking(depth + 1, currentCount+1);
					}
					else
					{
						backTracking(depth + 1, currentCount);
					}
				}
				isVisited[i] = false;
			}
		}
	}
}

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

	cin >> N;
	index = new int[N];
	str = new string[N];
	isVisited = new bool[N];
	for (int i = 0; i < N; i++)
	{
		isVisited[i] = false;
		cin >> str[i];
		for (int j = 1; j < str[i].length(); j++)
		{
			if (str[i].at(j) != str[i].at(j - 1))
			{
				middles++;
			}
		}
	}
	backTracking(0, middles);
	cout << answer << "\n";
	return 0;
}