알고리즘/programmers

[Programmers] 격자 뒤집기 미로

꾸준함. 2025. 3. 6. 10:34

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

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

 

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

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   

 

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

반응형

'알고리즘 > programmers' 카테고리의 다른 글

[Programmers] 경사로의 개수  (0) 2025.02.20
[Programmers] 봉인된 주문  (0) 2025.02.18
[Programmers] 완전범죄  (0) 2025.02.17
[Programmers] 서버 증설 횟수  (0) 2025.02.15
[Programmers] 홀짝트리  (10) 2025.02.14