[모의 SW 역량테스트] 보호 필름 - 2112

문제 : https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

코드 : 

1차시도 : 

#include <iostream>
#include <algorithm>

using namespace std;

int arr[13][20] = { 0 };
int D, W, K;
int result = 100;

bool calc()
{
	bool check = false;
	for (int i = 0; i < W; i++)
	{
		int count = 1;
		int temp = arr[0][i];
		for (int j = 1; j < D; j++)
		{
			if (arr[j][i] == temp)
				count++;
			else
			{
				temp = arr[j][i];
				count = 1;
			}

			if (count == K)
			{
				break;
			}
		}
		// 한 라인이라도 실패할 경우
		if (count < K)
		{
			return false;
		}
	}
	return true;
}

void solvLoop(int lineCount, int checkCount, int* changeArr)
{
	if (result != 100)
		return;

	if (checkCount == lineCount)
	{
		bool re = calc();
		if (re)
		{
			if (result > checkCount)
				result = checkCount;
			return;
		}
	}
	
	for (int i = checkCount; i < lineCount; i++)
	{
		int h = changeArr[i];
		int temp[20] = { 0 };
		for (int w = 0; w < W; w++)
		{
			temp[w] = arr[h][w];
			arr[h][w] = 0;
		}
		
		solvLoop(lineCount, i + 1, changeArr);
		for (int w = 0; w < W; w++)
		{
			arr[h][w] = 1;
		}
		solvLoop(lineCount, i + 1, changeArr);
		//원복
		for (int w = 0; w < W; w++)
		{
			arr[h][w] = temp[w];
		}
	}
}

void solution()
{
	int i = 0;
	int check[13] = { 0 }; // 투약 라인
	int lineTemp[13] = { 0 };//투약라인 인덱스 저장
	bool find = false;

	while (true)
	{
		do
		{
			int c = 0;
			for (int j = 0; j < D; j++)
			{
				if (check[j] == 1)
				{
					lineTemp[c++] = j;
				}
			}
			solvLoop(i, 0, lineTemp);
			if (result != 100)
			{
				find = true;
				break;
			}
		} while (prev_permutation(check, &check[D]));

		check[i] = 1;
		i++;
		if (find)
			break;
	}
}

int main()
{
	int count;
	cin >> count;

	int c = 0;
	while (c < count)
	{
		cin >> D >> W >> K;

		for (int i = 0; i < D; i++)
		{
			for (int j = 0; j < W; j++)
			{
				cin >> arr[i][j];
			}
		}
		result = 100;
		solution();
		c++;
		cout << "#" << c << " " << result << "\n";
	}


	return 0;
}

solution() : next_permutation을 사용하여 모든 약품투입 행을 탐색한다.

solvLoop() : DFS를 사용하여 A,B 투입의 경우의 수 를 계산한다.

Calc() : 성능검사 통과하는지 검사한다.

1차시도는 계속해서 케이스 49/50만 통과되어서 실패했다... 아직도 이유를 모르겠다..

시간초과로 인해 마지막 케이스가 실패하는데 왜 시간초과가 뜨는지..ㅠㅠ

2차시도 코드 :

#include <iostream>
#include <algorithm>

using namespace std;

int arr[13][20] = { 0 };
int D, W, K;
int result = 100;
int lineCount = 0;

bool Calc()
{
	int check[20] = { false };
	for (int j = 0; j < W; j++)
	{
		int fv = arr[0][j];
		int count = 1;
		for (int i = 1; i < D; i++)
		{
			if (fv == arr[i][j])
			{
				count++;
			}
			else
			{
				fv = arr[i][j];
				count = 1;
			}

			if (count == K)
			{
				break;
			}
		}
		if (count < K)
			return false;
	}

	return true;
}

void solution(int totalcount, int index, int count)
{
	if (result < count)
	{
		return;
	}
	if (totalcount == index)
	{
		//계산
		bool check = Calc();
		if (check)
		{
			if (result > count)
				result = count;
		}
		return;
	}

	solution(totalcount, index + 1, count);

	int temp[20] = { 0 };
	//A 약물투여
	for (int i = 0; i < W; i++)
	{
		temp[i] = arr[index][i];
		arr[index][i] = 0;
	}
	lineCount++;
	solution(totalcount, index + 1, count + 1);
	lineCount--;
	//B 약물투여
	for (int i = 0; i < W; i++)
	{
		arr[index][i] = 1;
	}
	lineCount++;
	solution(totalcount, index + 1, count + 1);
	lineCount--;
	//원상복귀
	for (int i = 0; i < W; i++)
	{
		arr[index][i] = temp[i];
	}
}

int main()
{
	int count;
	cin >> count;

	int c = 0;
	while (c < count)
	{
		cin >> D >> W >> K;

		for (int i = 0; i < D; i++)
		{
			for (int j = 0; j < W; j++)
			{
				cin >> arr[i][j];
			}
		}
		result = 100;
		lineCount = 0;
		solution(D, 0, 0);
		c++;
		cout << "#" << c << " " << result << "\n";
	}


	return 0;
}

solution() : DFS를 사용하여 약품을 투입할 경우, A 투입, B 투입 총 3가지 경우를 고려한다.

Calc() : 성능검사 통과하는지 검사한다.

이 문제는 순 완전탐색으로만 진행하면 케이스가 많아 시간초과가 난다. 

그러므로 최대한 최적화를 해줘야 한다.

1. DFS시 약품투입할 최소 행의 갯수를 찾았으면 이보다 큰 경우는 탐색할 필요없다.  

2. Calc에서는 처음에 열 단위로 모두 체크한 다음 한꺼번에 for문으로 실패한 열이 있는지 검색하는 방식으로 하였다.

이렇게 하니깐 시간오류에서 48/50으로 진전이 없었다. 해서 어차피 하나만 실패해도 탈락이니 이를 이용하여 해결하였다.

흐음.. 결론적으로 해결은 됐는데... 찝찝하다..

처음 코드는 왜 안되는것인지... 혹시 DFS만 써야하는건지... 불필요하여 permutation함수를 사용하여 그런건지.. 

혹시라도 이글을 보시는 분 중 아시는 분은 댓글 부탁드립니다~!!!