문제
문제가 길어 링크를 첨부했습니다.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
풀이
먼저 이 문제는 블럭들을 4방향으로 움직이고 합치는 것이 중점입니다.
이 것을 위해 매 단계마다 보드 전체를 탐색하며 블럭이 있으면 해당하는 방향으로 움직이고 합치기로 생각했습니다.
보드 크기는 최대 20이고 5번까지 움직일 수 있다 조건이 주어져 있어 최악의 경우 반복횟수는 으로 제가 생각하는 최대 반복횟수인 10억번에 미치지 않아 충분히 제한시간 안에 풀릴 것이라 생각했습니다.
이 문제의 충돌은 블록이 있는 칸에서 가장 마지막으로 탐색한 칸을 저장한 다음 해당하는 칸의 숫자가 현위치 블럭의 숫자와 같으면 충돌하게 구현하였습니다.
조건에서 충돌은 블럭 당 1번이라 그랬는데 이 충돌을 매 행이나 열마다 충돌 여부 배열을 만들어 이번 회차에 충돌했는지 여부를 기록하고 사용해 이 조건을 구현하였습니다.
충돌이 아닌 이동의 경우는 아까 사용했던 블럭이 있는 마지막 탐색 칸의 한 칸 앞으로 바로 이동시키는 것으로 구현했습니다.
이렇게 이동 및 충돌 구현은 쉬웠지만 정작 헤맸던 부분은 객체 수명 관리였습니다.
처음 시도하고 계속 오류가 났는데 시도하고 코드를 탐색하다 보니 아래와 같이 4방향으로 탐색할 때 같은 행렬을 사용하는 실수를 저질렀습니다.
vector<vector<int>> arr{q.front().second}; q.pop();
for (int i = 0; i < 4; ++i) { moveArr(arr, dx[i], dy[i]); ...이 것을 해결하기 위해 지역변수로 선언하고 참조로 넘겼더니 객체가 사라지는 문제가 있었고 결국엔 객체를 깊은 복사 생성자로 매 분기마다 복사하는 것으로 최종적으로 구현했습니다.
코드
#include <iostream>#include <queue>
using namespace std;
int N;
int dx[4]{1, -1, 0, 0};int dy[4]{0, 0, 1, -1};
void moveArr(vector<vector<int>>& arr, int deltaX, int deltaY){ if (deltaX > 0) { for (int j = 0; j < N; ++j) { int blockCol = N; // 블록이 있는 칸 중 열이 가장 작은 수 vector<bool> notMerge(N); for (int i = N - 1; i >= 0; --i) { if (arr[j][i] == 0) continue;
// 현위치 블록과 블록이 도착할 칸 다음 칸 블록이 같은 수라면 if (blockCol < N && arr[j][i] == arr[j][blockCol] && !notMerge[blockCol]) { arr[j][blockCol] *= 2; arr[j][i] = 0; notMerge[blockCol] = true; } else { arr[j][blockCol - 1] = arr[j][i]; if (blockCol - 1 != i) arr[j][i] = 0; blockCol -= 1; // 블록이 있는 칸 갱신 } } } } else if (deltaX < 0) { for (int j = 0; j < N; ++j) { int blockCol = -1; // 블록이 있는 칸 중 열이 가장 큰 수 vector<bool> notMerge(N); for (int i = 0; i < N; ++i) { if (arr[j][i] == 0) continue;
// 현위치 블록과 블록이 도착할 칸 다음 칸 블록이 같은 수라면 if (blockCol > -1 && arr[j][i] == arr[j][blockCol] && !notMerge[blockCol]) { arr[j][blockCol] *= 2; arr[j][i] = 0; notMerge[blockCol] = true; } else { arr[j][blockCol + 1] = arr[j][i]; if (blockCol + 1 != i) arr[j][i] = 0; blockCol += 1; // 블록이 있는 칸 갱신 } } } } else if (deltaY > 0) { for (int j = 0; j < N; ++j) { int blockRow = N; // 블록이 있는 칸 중 행이 가장 작은 수 vector<bool> notMerge(N); for (int i = N - 1; i >= 0; --i) { if (arr[i][j] == 0) continue;
// 현위치 블록과 블록이 도착할 칸 다음 칸 블록이 같은 수라면 if (blockRow < N && arr[i][j] == arr[blockRow][j] && !notMerge[blockRow]) { arr[blockRow][j] *= 2; arr[i][j] = 0; notMerge[blockRow] = true; } else { arr[blockRow - 1][j] = arr[i][j]; if (blockRow - 1 != i) arr[i][j] = 0; blockRow -= 1; // 블록이 있는 칸 갱신 } } } } else if (deltaY < 0) { for (int j = 0; j < N; ++j) { int blockRow = -1; vector<bool> notMerge(N); for (int i = 0; i < N; ++i) { if (arr[i][j] == 0) continue; if (blockRow > -1 && arr[i][j] == arr[blockRow][j] && !notMerge[blockRow]) { arr[blockRow][j] *= 2; arr[i][j] = 0; notMerge[blockRow] = true; } else { arr[blockRow + 1][j] = arr[i][j]; if (blockRow + 1 != i) arr[i][j] = 0; blockRow += 1; // 블록이 있는 칸 갱신 } } } }}
int bfs(const vector<vector<int>>& init){ queue<pair<int, vector<vector<int>>>> q;
q.push({0, init});
int result = 0;
while (!q.empty()) { const int level = q.front().first;
for (int i = 0; i < 4; ++i) { vector<vector<int>> arr(q.front().second); moveArr(arr, dx[i], dy[i]); if (level == 4) { int tmp = 0; for (int j = 0; j < N; ++j) for (int k = 0; k < N; ++k) result = arr[j][k] > result ? arr[j][k] : result; } else { q.push({level + 1, arr}); } } q.pop(); }
return result;}
int main(){ vector<vector<int>> arr; cin >> N;
arr.resize(N);
for (int i = 0; i < N; ++i) { arr[i].resize(N); for (int j = 0; j < N; ++j) { cin >> arr[i][j]; } }
cout << bfs(arr);}