이번에는 백준 12100번 2048 (Easy) 문제를 풀어보았습니다.
현재 보드에서 위, 아래, 왼쪽, 오른쪽 중 하나의 방향을 선택해 최대 5번 이동할 수 있습니다.
각 이동에서 같은 값을 가진 블록은 합쳐질 수 있지만, 한 번 합쳐진 블록은 같은 이동에서 다시 합쳐질 수 없습니다.
가능한 모든 이동 순서를 확인해야 하므로 DFS를 이용한 완전탐색과 백트래킹으로 해결하였습니다.
문제 설명
N × N 크기의 2048 게임판이 주어집니다.
한 번의 이동에서는 보드 위의 모든 블록을 다음 네 방향 중 하나로 이동시킬 수 있습니다.
- 위
- 아래
- 왼쪽
- 오른쪽
이동하는 방향에 있는 같은 값의 블록 두 개가 만나면 하나로 합쳐집니다.
단, 한 번의 이동에서 이미 합쳐진 블록은 다시 다른 블록과 합쳐질 수 없습니다.
최대 5번 이동하여 만들 수 있는 블록 중 가장 큰 값을 구하는 문제입니다.
풀이 아이디어
한 번 이동할 때 선택할 수 있는 방향은 총 4가지입니다.
이를 최대 5번 수행하므로 가능한 이동 순서의 수는 다음과 같습니다.
4⁵ = 1024경우의 수가 많지 않으므로 모든 이동 순서를 확인하는 완전탐색을 사용할 수 있습니다.
재귀 함수 solve()에서 현재 방향으로 블록을 이동시킨 뒤, 다시 네 방향에 대해 재귀 호출합니다.
재귀 호출이 끝난 후에는 다음 방향을 독립적으로 확인할 수 있도록 이동 전 보드 상태를 복구합니다.
블록 이동은 방향에 따라 각 행 또는 열의 0이 아닌 값을 스택에 저장한 뒤, 같은 값이 연속해서 나오면 두 값을 합치는 방식으로 구현하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
int ret = INT_MIN;
vector<vector<int>> inp;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
void check() {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
ret = max(ret, inp[i][j]);
}
}
}
void move(int y, int x) {
if (y == 0) {
if (x == -1) { // 0,-1 왼쪽 방향
for (int i=0; i<N; i++) {
stack<int> stk;
for (int j=0; j<N; j++) {
if (inp[i][j] == 0) continue;
stk.push(inp[i][j]);
}
int index=0;
while (!stk.empty()) {
int cur = stk.top();
stk.pop();
if (!stk.empty() && cur == stk.top()) {
cur *= 2;
stk.pop();
}
inp[i][index++] = cur;
}
for (int j=index; j<N; j++) {
inp[i][j] = 0;
}
}
} else { // 0,1 오른쪽 방향
for (int i=0; i<N; i++) {
stack<int> stk;
for (int j=N-1; j>=0; j--) {
if (inp[i][j] == 0) continue;
stk.push(inp[i][j]);
}
int index=N-1;
while (!stk.empty()) {
int cur = stk.top();
stk.pop();
if (!stk.empty() && cur == stk.top()) {
cur *= 2;
stk.pop();
}
inp[i][index--] = cur;
}
for (int j=index; j>=0; j--) {
inp[i][j] = 0;
}
}
}
} else {
if (y == -1) { // -1,0 위 방향
for (int i=0; i<N; i++) {
stack<int> stk;
for (int j=0; j<N; j++) {
if (inp[j][i] == 0) continue;
stk.push(inp[j][i]);
}
int index=0;
while (!stk.empty()) {
int cur = stk.top();
stk.pop();
if (!stk.empty() && cur == stk.top()) {
cur *= 2;
stk.pop();
}
inp[index++][i] = cur;
}
for (int j=index; j<N; j++) {
inp[j][i] = 0;
}
}
} else { // 1,0 아래 방향
for (int i=0; i<N; i++) {
stack<int> stk;
for (int j=N-1; j>=0; j--) {
if (inp[j][i] == 0) continue;
stk.push(inp[j][i]);
}
int index=N-1;
while (!stk.empty()) {
int cur = stk.top();
stk.pop();
if (!stk.empty() && cur == stk.top()) {
cur *= 2;
stk.pop();
}
inp[index--][i] = cur;
}
for (int j=index; j>=0; j--) {
inp[j][i] = 0;
}
}
}
}
}
void solve(int y, int x, int cnt) {
check();
if (cnt == 6) {
return;
}
move(y,x);
vector<vector<int>> tmp;
tmp.resize(N, vector<int>(N));
for (int i=0; i<4; i++) {
tmp = inp;
solve(dy[i],dx[i],cnt+1);
inp = tmp;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
inp.resize(N, vector<int>(N));
for(int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
cin >> inp[i][j];
}
}
if (N == 1) {
cout << inp[0][0];
return 0;
}
vector<vector<int>> tmp;
tmp.resize(N, vector<int>(N));
for (int i=0; i<4; i++) {
tmp = inp;
solve(dy[i], dx[i], 1);
inp = tmp;
}
cout << ret;
return 0;
}풀이 흐름
-
초기 게임판의 상태를 입력받습니다.
-
위, 아래, 왼쪽, 오른쪽 네 방향에 대해
solve()를 호출합니다. -
현재 보드에서 가장 큰 블록을 확인하여
ret을 갱신합니다. -
입력받은 방향으로 모든 블록을 이동시킵니다.
-
이동이 끝난 보드를 임시 배열에 저장합니다.
-
다시 네 방향에 대해 재귀 호출합니다.
-
재귀 호출이 끝나면 저장해 둔 보드 상태로 복구합니다.
-
최대 5번의 이동을 모두 확인한 뒤 가장 큰 블록을 출력합니다.
구현 포인트
1. 이동 방향 표현
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};각 인덱스는 다음 방향을 의미합니다.
(-1, 0) : 위
(1, 0) : 아래
(0, -1) : 왼쪽
(0, 1) : 오른쪽재귀 함수에 (y, x) 형태로 방향을 전달하여 어떤 방향으로 블록을 이동시킬지 구분하였습니다.
2. 현재 보드의 최대 블록 확인
void check() {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
ret = max(ret, inp[i][j]);
}
}
}현재 게임판의 모든 칸을 확인하면서 가장 큰 블록을 ret에 저장합니다.
문제에서는 반드시 정확히 5번 이동해야 하는 것이 아니라 최대 5번 이동할 수 있다고 하였으므로, 재귀의 각 단계마다 최대 블록을 확인합니다.
void solve(int y, int x, int cnt) {
check();이를 통해 5번보다 적게 이동한 상태에서 만들어진 최대 블록도 정답에 포함할 수 있습니다.
3. 모든 이동 순서 탐색
한 번의 이동마다 선택할 수 있는 방향은 총 4가지입니다.
for (int i=0; i<4; i++) {
tmp = inp;
solve(dy[i],dx[i],cnt+1);
inp = tmp;
}현재 이동 이후 다시 네 방향을 선택하여 재귀 호출합니다.
최대 이동 횟수가 5번이므로 전체 이동 순서의 수는 다음과 같습니다.
4 × 4 × 4 × 4 × 4 = 4⁵ = 1024가능한 경우의 수가 크지 않기 때문에 완전탐색으로 확인할 수 있습니다.
4. 재귀 종료 조건
if (cnt == 6) {
return;
}cnt는 현재 수행하려는 이동의 횟수를 나타냅니다.
처음 solve()를 호출할 때 cnt에 1을 전달하고, 재귀 호출마다 1씩 증가시킵니다.
cnt가 6이 되면 최대 5번의 이동을 모두 확인한 상태이므로 재귀를 종료합니다.
5. 보드 상태 복구
각 방향의 결과는 서로 영향을 주면 안 됩니다.
예를 들어 현재 보드에서 위쪽으로 이동한 결과를 확인한 뒤, 오른쪽으로 이동하는 경우를 확인할 때는 다시 위쪽으로 이동하기 전 상태에서 시작해야 합니다.
이를 위해 현재 보드 상태를 tmp에 저장합니다.
tmp = inp;
solve(dy[i],dx[i],cnt+1);
inp = tmp;재귀 호출이 끝나면 inp를 이전 상태로 복구합니다.
이 과정은 DFS에서 선택한 상태를 다시 원래 상태로 돌리는 백트래킹에 해당합니다.
6. 이동 방향에 따른 행과 열 선택
move() 함수에서는 전달된 (y, x) 값으로 이동 방향을 구분합니다.
if (y == 0)이면 좌우 이동입니다.
x == -1: 왼쪽 이동x == 1: 오른쪽 이동
반대로 y가 0이 아니라면 상하 이동입니다.
y == -1: 위쪽 이동y == 1: 아래쪽 이동
방향에 따라 행 단위 또는 열 단위로 블록을 확인합니다.
7. 빈칸을 제외하고 블록 저장
블록을 이동할 때 값이 0인 칸은 빈칸이므로 스택에 넣지 않습니다.
if (inp[i][j] == 0) continue;
stk.push(inp[i][j]);0을 제외하고 실제 블록만 저장하면, 블록들이 이동 방향으로 밀착된 상태를 만들 수 있습니다.
예를 들어 다음과 같은 행이 있다면
2 0 2 00을 제외한 블록만 저장하여
2 2처럼 처리할 수 있습니다.
8. 같은 값의 블록 합치기
스택에서 현재 블록을 하나 꺼냅니다.
int cur = stk.top();
stk.pop();이후 다음 블록이 존재하고 현재 블록과 값이 같다면 두 블록을 합칩니다.
if (!stk.empty() && cur == stk.top()) {
cur *= 2;
stk.pop();
}두 블록을 합치면 현재 값 cur을 두 배로 만들고, 합쳐진 다음 블록도 스택에서 제거합니다.
합쳐진 결과는 바로 게임판에 배치하며 다시 스택에 넣지 않습니다.
따라서 한 번의 이동에서 이미 합쳐진 블록이 다시 다른 블록과 합쳐지는 것을 방지할 수 있습니다.
9. 이동 방향에 따른 탐색 순서
2048에서는 블록을 이동시키는 방향에 가까운 블록부터 먼저 합쳐져야 합니다.
따라서 방향에 따라 블록을 탐색하는 순서를 다르게 설정하였습니다.
왼쪽 이동
for (int j=0; j<N; j++)왼쪽에서 오른쪽으로 행을 확인합니다.
결과를 저장하는 위치는 0부터 시작합니다.
int index=0;
inp[i][index++] = cur;오른쪽 이동
for (int j=N-1; j>=0; j--)오른쪽에서 왼쪽으로 행을 확인합니다.
결과는 오른쪽 끝인 N-1부터 저장합니다.
int index=N-1;
inp[i][index--] = cur;위쪽 이동
for (int j=0; j<N; j++)위쪽에서 아래쪽으로 열을 확인합니다.
결과는 가장 위쪽 행부터 저장합니다.
int index=0;
inp[index++][i] = cur;아래쪽 이동
for (int j=N-1; j>=0; j--)아래쪽에서 위쪽으로 열을 확인합니다.
결과는 가장 아래쪽 행부터 저장합니다.
int index=N-1;
inp[index--][i] = cur;10. 이동 후 남은 칸 초기화
블록을 합치고 이동시킨 뒤에는 블록이 채워지지 않은 나머지 칸을 0으로 만들어야 합니다.
왼쪽 이동의 경우 다음과 같이 처리합니다.
for (int j=index; j<N; j++) {
inp[i][j] = 0;
}오른쪽 이동에서는 index 왼쪽에 남아 있는 칸을 0으로 만듭니다.
for (int j=index; j>=0; j--) {
inp[i][j] = 0;
}상하 이동도 같은 방식으로 남은 칸을 초기화합니다.
이를 통해 이전 보드에 있던 값이 남지 않도록 합니다.
11. N이 1인 경우
if (N == 1) {
cout << inp[0][0];
return 0;
}보드 크기가 1이면 이동시킬 수 있는 다른 칸이 없습니다.
따라서 처음 주어진 하나의 블록이 그대로 최댓값이 되므로 바로 출력합니다.
12. DFS와 백트래킹
이 풀이는 가능한 모든 이동 순서를 재귀적으로 탐색하므로 DFS를 사용합니다.
solve(dy[i],dx[i],cnt+1);또한 각 방향에 대한 탐색이 끝난 뒤 보드 상태를 복구합니다.
tmp = inp;
solve(dy[i],dx[i],cnt+1);
inp = tmp;따라서 이 풀이는 DFS를 이용한 완전탐색과 백트래킹 방식이라고 볼 수 있습니다.
13. 시간복잡도
한 번 이동할 때 전체 게임판을 확인하므로 O(N²)의 시간이 필요합니다.
가능한 이동 순서는 최대 4⁵개입니다.
따라서 전체 시간복잡도는 다음과 같습니다.
O(4⁵ × N²)4⁵는 1024이고 N은 최대 20이므로 충분히 해결할 수 있습니다.
