[Programmers] 격자 뒤집기 미로

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/389630

프로그래머스

 

비트마스크를 통해 풀 수 있는 문제였습니다.

 

알고리즘은 다음과 같습니다.

1. 격자의 모든 칸의 visible 값을 더해 기본 점수를 구하고, 각 칸에서 hidden과 visible의 차이를 diff로 계산합니다.

 

2. 각 행을 뒤집거나 그대로 두는 모든 경우 {2^(행 수}) 가지를 고려하여, 뒤집힌 행의 수에 따른 비용을 기본 점수에서 차감해 기준 점수를 정합니다.

 

3. 각 열에서 "열을 그대로 둘 때”와 “열을 뒤집을 때”의 추가 이득과, 체스판에서 홀수 위치 셀의 최소 점수를 각각 계산합니다.

• 각 열을 처리할 때는 두 가지 선택지가 있음
  • 열을 그대로 둘 때는 해당 열에서 행 상태에 따라, 뒤집힌 행의 경우에는 diff가 적용되어 추가 이득이 생기고, 뒤집히지 않은 행은 변화가 없으므로 그 셀의 값은 그대로 유지
  • 열을 뒤집을 때는 반대로 뒤집히지 않은 행에만 diff가 적용되며, 뒤집힌 행은 변화가 없으므로 이득이 생기지 않는데, 여기에 열을 뒤집는 비용 k가 추가로 차감됨

 

• 해밀턴 경로가 불가능할 경우 한 칸을 빼야 하므로 각 열의 체스판 홀수 위치에 있는 셀들의 점수를 계산
  • 행이 뒤집혔고 열이 뒤집히지 않았을 때 홀수 셀의 점수는 visible+diff가 되고, 열이 뒤집혔을 때는 visible만 적용
  • 반면 행이 뒤집히지 않았다면 위 두 경우가 반대로 적용

 

4. 전체 격자에서 모든 칸을 방문할 수 있는지, 즉 해밀턴 경로가 가능한지 여부를 판단합니다.

 

5. 해밀턴 회로가 가능하면 각 열을 뒤집었을 경우와 뒤집지 않았을 경우를 비교했을 때 더 큰 이득을 선택하면 됩니다.

 

5.1 해밀턴 경로가 불가능한 경우에는 모든 칸을 방문할 수 없으므로, 한 칸의 홀수 위치 셀을 경로에서 제외해야 합니다.

이때 최종 점수는 기준 점수와 각 열에서 선택된 옵션들의 이득 합계에서, 선택된 옵션들의 홀수 위치 셀 값들 중 전역 최소값을 빼서 계산됩니다.

• 문제는, 만약 한 열에서 선택된 옵션의 홀수 점수가 지나치게 낮을 경우 해당 열이 전체 전역 최소 홀수 점수를 결정하게 되어 최종 점수에서 큰 페널티가 발생
• 단순히 각 열에서 최고 profit 옵션만 선택하면, 낮은 홀수 점수가 포함되어 전역 최소값이 낮아지고, 최종 점수가 떨어질 위험 존재
• 위 두 문제를 해결하기 위해 threshold 개념을 도입 (코드 주석 참고)

 

6. 모든 행 뒤집기 경우에서 산출된 최종 점수 중 가장 큰 값을 결과로 반환합니다.

 

	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	const int INF = 1e9;
	const int NEG_INF = -1e9;
	int getOneBitCnt(int mask)
	{
	int result = 0;
	while (mask)
	{
	result += mask % 2;
	mask /= 2;
	}
	return result;
	}
	int solution(vector<vector<int>> visible, vector<vector<int>> hidden, int k) {
	int nRows = visible.size();
	if (nRows == 0)
	{
	return 0;
	}
	int nCols = visible[0].size();
	int initSum = 0;
	for (int i = 0; i < nRows; i++)
	{
	for (int j = 0; j < nCols; j++)
	{
	initSum += visible[i][j];
	}
	}
	vector<vector<int>> diff(nRows, vector<int>(nCols, 0));
	for (int i = 0; i < nRows; i++)
	{
	for (int j = 0; j < nCols; j++)
	{
	diff[i][j] = hidden[i][j] - visible[i][j];
	}
	}
	bool canVisitAllCells = false;
	if (nRows >= 2 && nCols >= 2)
	{
	if (((nRows + nCols) % 2 == 0) && ((nRows * nCols) % 2 == 0))
	{
	canVisitAllCells = true;
	}
	}
	int answer = NEG_INF;
	for (int rowMask = 0; rowMask < (1 << nRows); rowMask++)
	{
	int flipCount = getOneBitCnt(rowMask);
	int rowCost = flipCount * k;
	int baseScore = initSum - rowCost;
	vector<int> colFlippedSum(nCols, 0), colNotFlippedSum(nCols, 0);
	for (int col = 0; col < nCols; col++)
	{
	int sumFlipped = 0, sumNotFlipped = 0;
	for (int row = 0; row < nRows; row++)
	{
	if (rowMask & (1 << row))
	{
	sumFlipped += diff[row][col];
	}
	else
	{
	sumNotFlipped += diff[row][col];
	}
	}
	colFlippedSum[col] = sumFlipped;
	colNotFlippedSum[col] = sumNotFlipped;
	}
	if (!canVisitAllCells)
	{
	int colTotalScore = 0;
	for (int col = 0; col < nCols; col++)
	{
	colTotalScore += max(colFlippedSum[col], colNotFlippedSum[col] - k);
	}
	answer = max(answer, baseScore + colTotalScore);
	}
	else
	{
	vector<int> minOddScoreColNotFlipped(nCols, INF);
	vector<int> minOddScoreColFlippped(nCols, INF);
	for (int col = 0; col < nCols; col++)
	{
	for (int row = 0; row < nRows; row++)
	{
	// 홀수 위치 중 하나를 방문할 수 없음
	if (((row + col) & 1) == 1)
	{
	int oddScoreColNotFlipped;
	int oddScoreColFlipped;
	// 행 뒤집힌 경우
	if (rowMask & (1 << row))
	{
	oddScoreColNotFlipped = visible[row][col] + diff[row][col];
	oddScoreColFlipped = visible[row][col];
	}
	// 행 그대로인 경우
	else
	{
	oddScoreColNotFlipped = visible[row][col];
	oddScoreColFlipped = visible[row][col] + diff[row][col];
	}
	minOddScoreColNotFlipped[col]
	= min(minOddScoreColNotFlipped[col], oddScoreColNotFlipped);
	minOddScoreColFlippped[col]
	= min(minOddScoreColFlippped[col], oddScoreColFlipped);
	}
	}
	}
	// 최종 점수 = baseScore + (모든 열의 이득 합계) – (전역 최소 홀수 점수)
	// 각 열에 대해 profit과 홀수 점수 두 가지를 동시에 고려해야 하는데,
	// 최종적으로 모든 열이 일정 수준(threshold) 이상의 홀수 점수를 가지도록 옵션을 선택할 경우,
	// 각 열의 선택들이 너무 낮은 홀수 점수를 내지 않게 되어 전체적으로 profit과 홀수 점수 간의 균형을 맞출 수 있음
	vector<int> thresholds;
	for (int col = 0; col < nCols; col++)
	{
	thresholds.push_back(minOddScoreColNotFlipped[col]);
	thresholds.push_back(minOddScoreColFlippped[col]);
	}
	sort(thresholds.begin(), thresholds.end());
	thresholds.erase(unique(thresholds.begin(), thresholds.end()), thresholds.end());
	int bestScore = NEG_INF;
	// 각 후보 threshold에 대해, 모든 열에서 해당 임계값 이상인 홀수 점수를 보장하는 옵션들을 선택할 수 있는지 확인
	for (int threshold : thresholds)
	{
	bool valid = true;
	int profitSum = 0;
	int globalOddMin = INF;
	for (int col = 0; col < nCols; col++)
	{
	// bestColProfit은 현재 열에서 threshold 조건을 만족하는 옵션 중 최대 추가 이득(profit)을 저장
	int bestColProfit = NEG_INF;
	// chosenOdd는 선택된 옵션에서의 최소 홀수 점수를 기록
	int chosenOdd = INF;
	if (minOddScoreColNotFlipped[col] >= threshold)
	{
	bestColProfit = colFlippedSum[col];
	chosenOdd = minOddScoreColNotFlipped[col];
	}
	if (minOddScoreColFlippped[col] >= threshold)
	{
	int profitOpt = colNotFlippedSum[col] - k;
	if (profitOpt > bestColProfit)
	{
	bestColProfit = profitOpt;
	chosenOdd = minOddScoreColFlippped[col];
	}
	}
	if (bestColProfit == NEG_INF)
	{
	valid = false;
	break;
	}
	profitSum += bestColProfit;
	globalOddMin = min(globalOddMin, chosenOdd);
	}
	if (valid)
	{
	bestScore = max(bestScore, baseScore + profitSum - globalOddMin);
	}
	}
	answer = max(answer, bestScore);
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE   

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~