2020.02.12
Solution
inMap : input map
nextMap : 2048 게임이 진행됨에 따라 변경되는 map
dirInfo : 완전탐색으로 1번째~5번째에 블락을 이동시키는 방향을 결정해둔 배열
myQ : 코드 1의 방식에서 사용될 Q
check : 코드 2의 방식에서 사용될 bool 배열
알고리즘
- 기본적으로 5번의 턴에 사용될 방향을 완전탐색을 이용해 경우의 수를 구한다. O(4^5)
- 각 경우의 수 마다 5번의 턴을 수행시키고 최댓값을 갖는 블락의 수를 출력한다. 턴을 수행하는 방식은 기본적으로 방향에 따라 행/열 마다 블락들을 이동시키도록 구상하였다. 각 행/열 에서 블락들을 이동시키는 방식을 두 가지로 구현해보았다.
Solution1
- 옮기는 방향의 끝 index 부터 반대쪽 끝 index까지 탐색한다.
- 탐색하면서 0이 아닌 블락을 찾는다.
- 블락을 찾으면 cnt를 증가시켰고 이전 블락의 값과 비교하여 같은 블락이 2번 나온다면(연속한 것임) Q에 값을 2배하여 담는다. cnt를 0으로 설정한다.
- 블락을 찾지 못하면 그냥 지나간다.
- 다른 블락이 이어서 나온다면 다음 블락을 이전 블락값에 넣고 이전 블락값을 Q에 담는다. cnt를 1로 설정한다.
- 탐색이 끝났을 때 cnt가 0이 아닌 경우에는 Q에 담지않은 블락이 존재하는 것이므로 마지막으로 담겨있는 이전값을 Q에 담는다.
- 담는 과정이 끝났으므로 Q의 front부터 옮기는 방향의 끝 index부터 연속해서 담고 나머지 index에는 0을 담는다.
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 25;
int dirInfo[10]; // up : 0 down : 2 left : 1 right : 3
int newMap[MAX][MAX];
int inMap[MAX][MAX];
int N;
queue <int> myQ;
void print() {
printf("\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", newMap[i][j]);
}
printf("\n");
}
}
int mapCopy(int reset) {
int maxRet = -1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (reset == 1) {
if (maxRet < newMap[i][j]) maxRet = newMap[i][j];
newMap[i][j] = 0;
}
else newMap[i][j] = inMap[i][j];
}
}
return maxRet;
}
bool inRange(int idx) {
if (idx >= 0 && idx < N) return true;
else return false;
}
void doNext(int& _prev, int& _cur,int& _cnt) {
if (_prev == 0) {
_cnt = 1;
_prev = _cur;
}
else {
if (_cur == _prev) {
_cnt = 0;
myQ.push(_prev * 2);
_prev = 0;
}
else {
myQ.push(_prev);
_prev = _cur;
}
}
}
int getMax() {
mapCopy(0);
//print();
int tmp;
for (int m = 0; m < 5; m++) {
int nextDir = dirInfo[m];
//printf("direction : %d\n", nextDir);
if (nextDir & 1) {
for (int i = 0; i < N; i++) {
int cnt = 0;
int prev = 0;
if (int(nextDir / 2) > 0) {
for (int j = N - 1; j >= 0; j--) {
int cur = newMap[i][j];
if (cur == 0) continue;
doNext(prev, cur,cnt);
}
if (cnt != 0) myQ.push(prev);
int idx = N - 1;
while (!myQ.empty()) {
newMap[i][idx] = myQ.front();
myQ.pop();
idx--;
}
for (int j = idx; j >= 0; j--) newMap[i][j] = 0;
}
else {
int cnt = 0;
int prev = 0;
for (int j = 0; j < N; j++) {
int cur = newMap[i][j];
if (cur == 0) continue;
doNext(prev, cur, cnt);
}
if (cnt != 0) myQ.push(prev);
int idx = 0;
while (!myQ.empty()) {
newMap[i][idx] = myQ.front();
myQ.pop();
idx++;
}
for (int j = idx; j < N; j++) newMap[i][j] = 0;
}
}
}
else {
for (int j = 0; j < N; j++) {
if (int(nextDir / 2) > 0) {
int cnt = 0;
int prev = 0;
for (int i = N - 1; i >= 0; i--) {
int cur = newMap[i][j];
if (cur == 0) continue;
doNext(prev, cur, cnt);
}
if (cnt != 0) myQ.push(prev);
int idx = N - 1;
while (!myQ.empty()) {
newMap[idx][j] = myQ.front();
myQ.pop();
idx--;
}
for (int i = idx; i >= 0; i--) newMap[i][j] = 0;
}
else {
int cnt = 0;
int prev = 0;
for (int i = 0; i < N; i++) {
int cur = newMap[i][j];
if (cur == 0) continue;
doNext(prev, cur, cnt);
}
if (cnt != 0) myQ.push(prev);
int idx = 0;
while (!myQ.empty()) {
newMap[idx][j] = myQ.front();
myQ.pop();
idx++;
}
for (int i = idx; i < N; i++) newMap[i][j] = 0;
}
}
}
//print();
}
//print();
return mapCopy(1);
}
int getResult(int n) {
if (n >= 5) {
return getMax();
}
else {
int maxResult = -1;
for (int dir = 0; dir < 4; dir++) {
dirInfo[n] = dir;
int tmpResult = getResult(n + 1);
if (tmpResult > maxResult) maxResult = tmpResult;
}
return maxResult;
}
}
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &inMap[i][j]);
}
}
printf("%d\n", getResult(0));
return 0;
}Solution2
- 마찬가지로 옮기는 방향의 끝 index 부터 반대쪽 끝 index까지 탐색한다.
- 블락을 찾으면 옮기는 방향의 끝과 가장 가까운 빈칸을 찾는다.
- 만약 빈칸 다음이 벽이 아닌 다른 블락이라면 check 배열에 체크가 되어있는지 확인한다.(체크되어있다면 이미 합쳐진 블락이다.)
- 체크가 되어있다면 빈칸에 2에서 찾은 블락을 담는다.
- 체크가 되어있지 않다면 2-1에서 찾은 블락과 2에서 찾은 블락의 값을 비교하고 같다면 2-1에서 찾은 블락에 값을 2배 하여 담고 check 배열에 체크해둔다.
- 벽이라면 벽 전의 빈칸에 2에서 찾은 블락을 담는다.
- 만약 빈칸 다음이 벽이 아닌 다른 블락이라면 check 배열에 체크가 되어있는지 확인한다.(체크되어있다면 이미 합쳐진 블락이다.)
- 탐색이 끝나면 모두 옮겨져있게 된다.
#include<cstdio>
using namespace std;
const int MAX = 25;
int dirInfo[10]; // up : 0 down : 2 left : 1 right : 3
int newMap[MAX][MAX];
int inMap[MAX][MAX];
int N;
bool check[MAX];
void print() {
printf("\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", newMap[i][j]);
}
printf("\n");
}
}
int mapCopy(int reset) {
int maxRet = -1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (reset == 1) {
if (maxRet < newMap[i][j]) maxRet = newMap[i][j];
newMap[i][j] = 0;
}
else newMap[i][j] = inMap[i][j];
}
}
return maxRet;
}
bool inRange(int idx) {
if (idx >= 0 && idx < N) return true;
else return false;
}
int move(int idx, int start,int d, int RC) {
int ret;
if (RC == 1) { // x축
int curVal = newMap[idx][start];
newMap[idx][start] = 0;
int nextIdx = start + d;
while (inRange(nextIdx) && newMap[idx][nextIdx] == 0) nextIdx += d;
if (!inRange(nextIdx) || check[nextIdx] || newMap[idx][nextIdx] != curVal) {
nextIdx -= d;
newMap[idx][nextIdx] = curVal;
}
else {
check[nextIdx] = true;
newMap[idx][nextIdx] = curVal * 2;
}
ret = newMap[idx][nextIdx];
}
else if (RC == 2) { // y축
int curVal = newMap[start][idx];
newMap[start][idx] = 0;
int nextIdx = start + d;
while (inRange(nextIdx) && newMap[nextIdx][idx] == 0) nextIdx += d;
if (!inRange(nextIdx) || check[nextIdx] || newMap[nextIdx][idx] != curVal) {
nextIdx -= d;
newMap[nextIdx][idx] = curVal;
}
else {
check[nextIdx] = true;
newMap[nextIdx][idx] = curVal * 2;
}
ret = newMap[nextIdx][idx];
}
return ret;
}
int getMax() {
mapCopy(0);
//print();
int tmp;
for (int m = 0; m < 5; m++) {
int nextDir = dirInfo[m];
//printf("direction : %d\n", nextDir);
if (nextDir & 1) {
for (int i = 0; i < N; i++) {
for (int c = 0; c < N; c++) check[c] = false;
if (int(nextDir / 2) > 0) {
for (int j = N - 1; j >= 0; j--) {
if (newMap[i][j] == 0) continue;
tmp = move(i, j,1, 1);
}
}
else {
for (int j = 0; j < N; j++) {
if (newMap[i][j] == 0) continue;
tmp = move(i, j, -1, 1);
}
}
}
}
else {
for (int j = 0; j < N; j++) {
for (int c = 0; c < N; c++) check[c] = false;
if (int(nextDir / 2) > 0) {
for (int i = N - 1; i >= 0; i--) {
if (newMap[i][j] == 0) continue;
tmp = move(j, i, 1, 2);
}
}
else {
for (int i = 0; i < N; i++) {
if (newMap[i][j] == 0) continue;
tmp = move(j, i, -1, 2);
}
}
}
}
//print();
}
//print();
return mapCopy(1);
}
int getResult(int n) {
if (n >= 5) {
return getMax();
}
else {
int maxResult = -1;
for (int dir = 0; dir < 4; dir++) {
dirInfo[n] = dir;
int tmpResult = getResult(n + 1);
if (tmpResult > maxResult) maxResult = tmpResult;
}
return maxResult;
}
}
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &inMap[i][j]);
}
}
printf("%d\n", getResult(0));
return 0;
}실수
- 완전탐색을 할 때 dir을 5개만 정하고 그 안에서 최대를 찾는 문제인데 getResult 함수의 기저조건을 n>=N으로 설정했었다. O(4^5) 여야 하는 완전탐색문이 O(4^N)이 되었으니 최악의 경우에 O(2^40)이 되어 시간초과가 발생했다. 이를 모르고 완전탐색 이후 시간복잡도상 곱해지는 2048의 한 턴에서 이뤄지는 시간복잡도를 개선하려고 노력했으니 정작 중요한 시간초과 에러를 해결하지 못한 것이었다.
- 코드2가 기존의 풀이였는데 애초에 check bool 배열을 초기화 해가면서 써야하는데 이를 함수 초반에만 초기화 해주었었다. 오답이 발생하였고, 이 배열은 2048의 한 턴에서 행 혹은 열을 한칸씩 이동하며 블락을 이동시키기 전에 초기화를 시켜주며 사용해야 했다.
'SW > 알고리즘 문제풀이' 카테고리의 다른 글
| BJ5373 큐빙 (0) | 2020.02.14 |
|---|---|
| BJ16235 나무재테크 (0) | 2020.02.12 |
| BJ17142 연구소3 (0) | 2020.02.11 |
| BJ13460 구슬탈출2 (0) | 2020.02.10 |
| BJ15683 감시 (0) | 2020.02.10 |
Comment