www.acmicpc.net/workbook/view/1152 (A형 문제집)
2048 게임을 구현하는 문제,
구슬 탈출 2와 마찬가지로 4방향으로 움직이며, 총 5회까지 가능하다.
즉 45=1024번 의 경우의 수 중 가장 큰 값을 구하면 된다.
만들어야 함수는 다음과 같다.
1) input 함수 및 디버깅을 위한 output 함수.
2) Map에서 가장 큰 값을 찾는 함수.
3) 2차원 배열 초기화 함수, copy 함수.
4) move 함수. (Left, Up, Right, Down)
1) ~ 3) 함수는 취향대로 만들자.
A형에서는 라이브러리를 사용해도 되므로 memset, memcpy를 익혀두는 것도 괜찮다.
(하지만 B형에서는 사용할 수 없다는 것을 참고하자)
/* 2차원 배열에서 max 찾는 함수 */
int findMax(int map[][MAX])
{
int max = 0;
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (max < map[r][c]) max = map[r][c];
return max;
}
/* 2차원 배열 초기화 */
void memset0(int map[][MAX])
{
for (int r = 0; r < MAX; r++)
for (int c = 0; c < MAX; c++)
map[r][c] = 0;
}
/* 2차원 배열 복사, dest가 src로 변한다. */
void mapCopy(int dest[][MAX], int src[][MAX])
{
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
dest[r][c] = src[r][c];
}
이제 move 함수 = Left 를 만들자.
이미 합쳐진 블록은 또 다른 블록과 합쳐질 수 없다는 조건을 만족시켜야 한다.
즉 [2, 2, 2, 2] 가 Left로 이동하면 [8, 0, 0, 0]이 아닌 [4, 4, 0, 0]이 되어야 한다.
먼저 임시 2차원 배열을 초기화 하고, 합쳐지는 것과는 상관 없이 모든 배열을 왼쪽으로 옮긴다.
int tmp[MAX][MAX] = { 0 };
memset0(tmp);
for (int r = 0; r < N;r++)
{
int step = 0;
for (int c = 0; c < N; c++)
{
if (map[r][c] == 0) continue;
tmp[r][step++] = map[r][c];
}
}map이 빈칸인 경우는 넘어가고, 빈칸이 아닌 경우는 step 변수를 올려가면서 하나씩 왼쪽부터 쌓아 올린다.
이러면 [2, 0, 4, 0]이 [2, 4, 0, 0]으로 바뀌게 된다.
map에 그대로 복사하지 않는 이유는,
[2, 0, 4, 0] 이 [2, 4, 4, 0] 으로 되고 원래 4를 0으로 바꿔줘야하는 번거로움이 있기 때문이다.
따라서 0으로 초기화된 배열 tmp를 만들어서 왼쪽으로 옮기자.
이제 합쳐진 블록이 존재하는지 확인하고, 블록을 합치자.
map[r][c]와 map[r][c + 1]이 다르다면, 합쳐질 수 없으므로 continue.
합쳐질 수 있다면, map[r][c]를 2배로 만들고, 남은 배열을 1칸씩 당겨준다.
최종 코드는 아래와 같다.
void moveLeft(int map[][MAX])
{
int tmp[MAX][MAX] = { 0 };
memset0(tmp);
for (int r = 0; r < N;r++)
{
/* 일단 왼쪽으로 옮긴다. */
int step = 0;
for (int c = 0; c < N; c++)
{
if (map[r][c] == 0) continue;
tmp[r][step++] = map[r][c];
}
/* 합친다. */
for (int c = 0; c < N - 1; c++)
{
/* 다르면 합칠 수 없다. */
if (tmp[r][c] != tmp[r][c + 1]) continue;
else /* 같으면 */
{
tmp[r][c] *= 2; // tmp[r][c] = tmp[r][c] + tmp[r][c + 1];
/* 한칸 씩 옮긴다. */
for (int cc = c + 1; cc < N - 1; cc++) tmp[r][cc] = tmp[r][cc + 1];
tmp[r][N - 1] = 0;
}
}
}
mapCopy(map, tmp);
}이때, tmp[r][N - 1] = 0으로 만들어 주는 이유는, 한칸 씩 옮기기만 하면 마지막 변수가 남게 되기 때문이다.
( ex : [2, 0, 4, 4] => [2, 4, 4, 4] => tmp[r][3] = 0 => [2, 4, 4, 0] )
move 함수 = Right는 0부터 시작하지말고 N - 1부터 거꾸로 하면 된다.
void moveRight(int map[][MAX])
{
int tmp[MAX][MAX] = { 0 };
memset0(tmp);
for (int r = 0; r < N;r++)
{
int step = N - 1;
for (int c = N - 1; c >= 0; c--)
{
if (map[r][c] == 0) continue;
tmp[r][step--] = map[r][c];
}
for (int c = N - 1; c > 0; c--)
{
if (tmp[r][c] != tmp[r][c - 1]) continue;
else
{
tmp[r][c] *= 2;
for (int cc = c - 1; cc > 0; cc--) tmp[r][cc] = tmp[r][cc - 1];
tmp[r][0] = 0;
}
}
}
mapCopy(map, tmp);
}
move Up, Down 함수의 경우 move Left, Right를 보고 r, c를 적절히 바꿔주도록 하자.
(최종 코드 참고)
이제 DFS를 이용해서 4방향으로 총 5번씩 움직여 보자.
구슬 탈출 2와 다른 점은, 갔던 방향으로 또 가봐야 한다.
이미 합쳐진 블록은 또 다른 블록과 합쳐질 수 없다는 조건을 기억하자.
[2, 2, 2, 2] => [4, 4, 0, 0] 이 되지만, 왼쪽으로 한번 갔으니, 다시 갈 필요 없다고 생각하면
[4, 4, 0, 0] => [8, 0, 0, 0] 의 경우의 수를 놓치게 된다.
DFS 5단계에서 최종 map의 가장 큰 블럭을 저장해두고 종료해야하고,
4방향으로 움직인 map을 다음 DFS에 넘겨주자.
이때, 함수 포인터를 이용하면 조금 더 코드가 깔끔해 진다.
#define LEFT (0)
#define UP (1)
#define RIGHT (2)
#define DOWN (3)
void(*pMove[5])(int map[][MAX]);
int ANSWER = 0;
void DFS(int L, int map[][MAX])
{
if (L > 5) /* 종료 조건 */
{
int maxBlock = findMax(map);
if (ANSWER < maxBlock) ANSWER = maxBlock;
return;
}
int copy[MAX][MAX] = { 0 };
memset0(copy);
for (int i = 0; i < 4;i++)
{
mapCopy(copy, map); /* copy에 현재 map 복사 */
pMove[i](copy); /* copy를 옮겨주고 */
DFS(L + 1, copy); /* 다음 DFS에 바뀐 copy를 넘긴다 */
}
}
int main(void)
{
input();
pMove[LEFT] = moveLeft;
pMove[UP] = moveUp;
pMove[RIGHT] = moveRight;
pMove[DOWN] = moveDown;
DFS(1, MAP);
printf("%d\n", ANSWER);
return 0;
}
함수 포인터를 이용해서 for i = 0, 1, 2, 3 을 LEFT, UP, RIGHT, DOWN으로 매핑 시켰다.
함수 포인터 사용이 어렵다면 억지로 사용하지 말고, if else를 사용하자.
for (int i = 0; i < 4;i++)
{
mapCopy(copy, map);
// pMove[i](copy);
if (i == 0) moveLeft(copy);
else if (i == 1) moveUp(copy);
else if (i == 2) moveRight(copy);
else if (i == 3) moveDown(copy);
DFS(L + 1, copy);
}A형에서 최적화에 너무 목숨 걸 필요 없다.
최종 코드는 다음과 같다.
#include <stdio.h>
#define MAX (20 + 5)
int N;
int MAP[MAX][MAX];
#define LEFT (0)
#define UP (1)
#define RIGHT (2)
#define DOWN (3)
void(*pMove[5])(int map[][MAX]);
void input()
{
scanf("%d", &N);
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
scanf("%d", &MAP[r][c]);
}
void output(int map[][MAX])
{
for (int i = 0; i < N;i++)
{
for (int k = 0; k < N;k++)
printf("%d ", map[i][k]);
putchar('\n');
}
}
int findMax(int map[][MAX])
{
int max = 0;
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (max < map[r][c]) max = map[r][c];
return max;
}
void memset0(int map[][MAX])
{
for (int r = 0; r < MAX; r++)
for (int c = 0; c < MAX; c++)
map[r][c] = 0;
}
void mapCopy(int dest[][MAX], int src[][MAX])
{
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
dest[r][c] = src[r][c];
}
void moveLeft(int map[][MAX])
{
int tmp[MAX][MAX] = { 0 };
memset0(tmp);
for (int r = 0; r < N;r++)
{
int step = 0;
for (int c = 0; c < N; c++)
{
if (map[r][c] == 0) continue;
tmp[r][step++] = map[r][c];
}
for (int c = 0; c < N - 1; c++)
{
if (tmp[r][c] != tmp[r][c + 1]) continue;
else
{
tmp[r][c] *= 2;
for (int cc = c + 1; cc < N - 1; cc++) tmp[r][cc] = tmp[r][cc + 1];
tmp[r][N - 1] = 0;
}
}
}
mapCopy(map, tmp);
}
void moveUp(int map[][MAX])
{
int tmp[MAX][MAX] = { 0 };
memset0(tmp);
for (int c = 0; c < N;c++)
{
int step = 0;
for (int r = 0; r < N; r++)
{
if (map[r][c] == 0) continue;
tmp[step++][c] = map[r][c];
}
for (int r = 0; r < N - 1; r++)
{
if (tmp[r][c] != tmp[r + 1][c]) continue;
else
{
tmp[r][c] *= 2;
for (int rr = r + 1; rr < N - 1; rr++) tmp[rr][c] = tmp[rr + 1][c];
tmp[N - 1][c] = 0;
}
}
}
mapCopy(map, tmp);
}
void moveRight(int map[][MAX])
{
int tmp[MAX][MAX] = { 0 };
memset0(tmp);
for (int r = 0; r < N;r++)
{
int step = N - 1;
for (int c = N - 1; c >= 0; c--)
{
if (map[r][c] == 0) continue;
tmp[r][step--] = map[r][c];
}
for (int c = N - 1; c > 0; c--)
{
if (tmp[r][c] != tmp[r][c - 1]) continue;
else
{
tmp[r][c] *= 2;
for (int cc = c - 1; cc > 0; cc--) tmp[r][cc] = tmp[r][cc - 1];
tmp[r][0] = 0;
}
}
}
mapCopy(map, tmp);
}
void moveDown(int map[][MAX])
{
int tmp[MAX][MAX] = { 0 };
memset0(tmp);
for (int c = 0; c < N;c++)
{
int step = N - 1;
for (int r = N - 1; r >= 0; r--)
{
if (map[r][c] == 0) continue;
tmp[step--][c] = map[r][c];
}
for (int r = N - 1; r > 0; r--)
{
if (tmp[r][c] != tmp[r - 1][c]) continue;
else
{
tmp[r][c] *= 2;
for (int rr = r - 1; rr > 0; rr--) tmp[rr][c] = tmp[rr - 1][c];
tmp[0][c] = 0;
}
}
}
mapCopy(map, tmp);
}
int ANSWER = 0;
void DFS(int L, int map[][MAX])
{
if (L > 5)
{
int maxBlock = findMax(map);
if (ANSWER < maxBlock) ANSWER = maxBlock;
return;
}
int copy[MAX][MAX] = { 0 };
memset0(copy);
for (int i = 0; i < 4;i++)
{
mapCopy(copy, map);
pMove[i](copy);
DFS(L + 1, copy);
}
}
int main(void)
{
input();
pMove[LEFT] = moveLeft;
pMove[UP] = moveUp;
pMove[RIGHT] = moveRight;
pMove[DOWN] = moveDown;
DFS(1, MAP);
printf("%d\n", ANSWER);
return 0;
}
실제 A형은 tc가 여러개이므로, input에 초기화 코드를 추가하고, 답변 출력 형식을 맞춰주자.
int main(void)
{
int T;
scanf("%d", &T);
pMove[LEFT] = moveLeft;
pMove[UP] = moveUp;
pMove[RIGHT] = moveRight;
pMove[DOWN] = moveDown;
for (int tc = 1; tc <= T; tc++)
{
input(); // input에 MAP 초기화 코드 추가
ANSWER = 0;
DFS(1, MAP);
printf("#%d %d\n", tc, ANSWER);
}
return 0;
}
'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글
| BOJ 14499 : 주사위 굴리기 (삼성 SW TEST A형) (0) | 2021.02.15 |
|---|---|
| BOJ 13458 : 시험 감독 (삼성 SW TEST A형) (0) | 2021.02.15 |
| BOJ 3190 : 뱀 (삼성 SW TEST A형) (0) | 2021.02.14 |
| BOJ 13460 : 구슬 탈출 2 (삼성 SW TEST A형) (0) | 2021.02.06 |
| 백준에서 삼성 SW 기출 문제 보는 방법 (0) | 2021.02.06 |
댓글