개요
https://softeer.ai/practice/6276
게임의 룰은 가로 세로 N칸의 차고(격자)가 있고, 각 차고에는 색깔이 있는 자동차가 하나씩 있다. 한 턴에 한 칸을 선택하며, 선택한 칸과 상하좌우 칸에 들어있는 자동차의 색이 같다면 모두 사라진다. 그리고 사라진 칸들과 연결된 칸들의 상하좌우 칸에 들어있는 자동차의 색이 같다면 함께 사라진다. (문제 하단 예시 참고.)
이때, 획득할 수 있는 점수는 사라진 자동차의 개수와 사라지는 차고 칸을 모두 포함하는 가장 작은 직사각형의 넓이의 합이다.
자동차들이 사라지고 나면 위에 있는 자동차들이 아래로 떨어져 빈 칸을 채운다. 위쪽에는 충분한 자동차들이 더 있어서 위에서 추가적으로 떨어지며 모든 칸을 채운다.
위에서 어떤 자동차들이 떨어질지는 입력으로 주어진다. 위와 같은 게임을 3차례 반복 했을 때, 주어진 조건에서 얻을 수 있는 가장 큰 점수를 계산하라.
접근 방식
-
굉장히 고려할 게 많았던 문제였다.
시뮬레이션은 세차례밖에 안 하고, 각 버튼을 눌렀을 때 퍼즐의 상황이 계속 변하기 때문에,
백트래킹을 통해 모든 경우를 체크해야 한다고 느꼈다. -
만들어둔 함수는 크게 보면 세개다.
-
기본적인 백트래킹 함수. 여기서 각 시뮬레이션을 담당한다.
인자로 현재 시뮬레이션 단계수인 curStep, 이전 시뮬레이션의 점수인 prevScore,
이전 시뮬레이션 끝난 후 퍼즐의 상태 &prevState를 넘겨준다. -
WhenBtnClicked함수. 시뮬레이션 curStep 단계에서 h,w좌표의 버튼을 눌렀을 때,
근처의 상하좌우 버튼들이 targetColor색인지 판별 후, 방문 배열을 체크해준다.
재귀를 통해 (h,w)버튼의 상하좌우 버튼들 뿐만 아니라
상하좌우 버튼들의 상하좌우 버튼들도 동일하게 체크해준다. -
DeleteBlock함수. whenBtnClicked 함수를 통해 체크해준 deleteVisited배열을 탐색 후,
true이면 맨 위부터 끌어내려서 새로운 퍼즐 state를 만든다.
-
-
방문 배열을 두개를 사용했다. visited배열과 deleteVisited배열이다.
두 개를 사용한 이유가 있다.
visited배열만 사용했더니, curStep 1레벨 에서 curStep2 레벨로 진행한 후,
다시 curStep1로 돌아왔을 때 문제가 생겼다.
이전 curStep1 단계에서 방문한 버튼들이 visited가 체크가 되어있어서
중복으로 버튼 체크하지 않았지만, 버튼 삭제를 할때 문제였다.
방문한 버튼들을 모두 삭제해버려서 현재 방문한 버튼 뿐만아니라
이전 시뮬레이션에서 방문한 버튼들도 다 사라진 것이다.따라서 deleteVisited배열도 함께 사용하여, whenBtnClicked함수에서
deleteVisited와 visited를 둘 다 체크해줬다.
DeleteBlock함수에선 deleteVisited만 체크하여 방문했다면 버튼을 삭제했다.
제일 중요한 부분인데, 각 버튼을 누를때마다 deleteVisited를 false로 초기화해줬다.
이렇게 초기화해야 현재 버튼을 눌렀을 때 해당 버튼 주위 값들만 삭제가 된다.
-
이런 식으로 구현을 해도 시간초과가 문제였다.
한계가 1초인데 1.08초를 찍어서 몇몇 테케가 불합격을 맞았다.
이런 저런 시도를 해보고 깨달은 건,
prevState를 vector<vector<int>> tmp로 복사하는 과정이 백트래킹에 포함되는 데,
이 부분이 시간을 많이 잡아먹는 것이었다.따라서 세 번째 시뮬레이션일때와 첫번재, 두번째 시뮬레이션일 때를 나눠서
세번째 시뮬레이션일 때, 매우 간소화 시켰다.
세번째 시뮬레이션일때는 퍼즐상태를 변화시켜도 변화 상태를 저장할 필요가 없으므로,
굳이 tmp 벡터를 생성해 복사하지 않아도 된다.
또한 블록을 삭제하는 부분도 제거하는 등 최적화를 시켰다.
전체 코드
#include<iostream>
#include<vector>
using namespace std;
//백트래킹용 (같은레벨일때 어떤 버튼 눌렀는지 확인용)
bool visited[3][15][15];
//각 레벨에서 현재 방문한 블록 지우기용 (위에 배열을 사용해버리면 한 레벨을 두 번째 방문시 이전 방문 블록까지 다 지워버림)
bool deleteVisited[15][15];
int N, MaxAns, blockMaxH=-16, blockMinH=16, blockMaxW=-16, blockMinW=16;
vector<vector<int>> v;
int dh[4] = { -1,1,0,0 };
int dw[4] = { 0,0,-1,1 };
//i,j를 눌렀을 때 근처 같은 색상 전부 true처리해주고,
//같은 갯수 몇 개인지 반환()
int WhenBtnClicked(int h, int w, int curStep, int targetColor,vector<vector<int>>& prev) {
int sum = 1;
for (int i = 0; i < 4; i++) {
int nextH = h + dh[i];
int nextW = w + dw[i];
if (nextH < 0 || nextW < 0 || nextW == N || nextH == N) continue;
if (prev[nextH + 2*N][nextW] != targetColor) continue;
if (visited[curStep][nextH][nextW]) continue;
blockMinH = blockMinH > nextH ? nextH : blockMinH;
blockMaxH = blockMaxH > nextH ? blockMaxH : nextH;
blockMinW = blockMinW > nextW ? nextW : blockMinW;
//멍청이!
blockMaxW = blockMaxW > nextW ? blockMaxW : nextW;
visited[curStep][nextH][nextW] = true;
deleteVisited[nextH][nextW] = true;
sum += WhenBtnClicked(nextH, nextW, curStep, targetColor,prev);
}
return sum;
}
void DeleteBlock(int curStep, vector<vector<int>>& prevState) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (deleteVisited[i][j]) {
//i의 원래 좌표
int iOrigin = i + 2 * N;
bool allFullfilled = true;
//맨위에서 부터 i의 원래 좌표까지 끌어내림
while (iOrigin != 0) {
//만약 현재 좌표값이 -1이라면 위에도 다 -1이므로 내릴 필요없음
if (prevState[iOrigin][j] == -1) {
allFullfilled = false;
break;
}
prevState[iOrigin][j] = prevState[iOrigin -1][j];
iOrigin--;
}
//allFullFilled이면 처음 삭제된 형태로 0,j값 -1로 설정해주기.
if (allFullfilled)
prevState[0][j] = -1;
}
}
}
}
void Backtracking(int curStep, int prevScore, vector<vector<int>>& prevState) {
//터치했을 때, 상하좌우 재귀탐색해서 같으면 사라짐
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[curStep][i][j]) continue;
if (curStep + 1 != 3) {
//재귀가 끝나고 다시 curStep레벨에 방문하게 되면 deleteVisited 초기화해줘야함
fill(&deleteVisited[0][0], &deleteVisited[N - 1][N], false);
visited[curStep][i][j] = true;
deleteVisited[i][j] = true;
int targetColor = prevState[i + 2 * N][j];
vector<vector<int>> tmp;
tmp.resize(N * 3);
copy(prevState.begin(), prevState.end(), tmp.begin());
//초기화해줘야함
blockMaxH = i, blockMinH = i, blockMaxW = j, blockMinW = j;
int score = WhenBtnClicked(i, j, curStep, targetColor, tmp) + prevScore;
int height = blockMaxH - blockMinH + 1;
int width = blockMaxW - blockMinW + 1;
score += height * width;
//삭제하는 부분은 다시 되돌려놔야하므로 삭제된 벡터는 따로 킵
DeleteBlock(curStep, tmp);
Backtracking(curStep + 1, score, tmp);
}
//현재 2단계일 때,
else {
visited[curStep][i][j] = true;
int targetColor = prevState[i + 2 * N][j];
blockMaxH = i, blockMinH = i, blockMaxW = j, blockMinW = j;
int score = WhenBtnClicked(i, j, curStep, targetColor, prevState) + prevScore;
int height = blockMaxH - blockMinH + 1;
int width = blockMaxW - blockMinW + 1;
score += height * width;
MaxAns = score > MaxAns ? score : MaxAns;
}
}
}
//한 레벨이 끝나고 되돌아올 때, visited가 false처리되야함(초기화) 왜냐면 현재 단계와 다르게 진행될것이므로
fill(&visited[curStep][0][0], &visited[curStep][N - 1][N], false);
}
int main(int argc, char** argv)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
v.resize(N*3);
int num;
for (int i = 0; i < 3 * N; i++) {
for (int j = 0; j < N; j++) {
cin >> num;
v[i].push_back(num);
}
}
Backtracking(0, 0, v);
cout << MaxAns;
return 0;
}