2048 (Easy)
문제: 2048 Easy (백준 12100번)
구조 분석
처음 이 문제를 보고 드는 생각은 bfs 또는 dfs를 이용할 수 있겠다는 것이었다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록의 수를 출력하는 문제였기 때문에 dfs를 이용해야겠다고 생각했다. 그런데 dfs의 노드에 무엇을 넣어야 하는지가 문제였다. Stack에 해당 보드 자체를 넣어서 매번 보드를 꺼내고 움직이고 push하는것이 비효율적이라고 생각했기 때문이다.
이런 생각을 가지고 힌트를 보니 brute-force와 back-tracking이 있었다. 해당 문제를 더 효율적이고 쉽게 풀기 위해서는 brute force와 back tracking 기법을 이용하고자 한다. 이를 쉽게 이용하기 위해서는 dfs 구조를 머릿속에 떠올려야 한다.
Dfs란 깊이 우선 탐색으로 tree의 max depth까지 탐색하여 정답을 찾는 기법이다. 만약 max depth까지 탐새을 했는데도 답이 없다면 이전 depth에서 expand된 다른 노드를 탐색한다. 이와 같은 방식은 back tracking을 구현하는데 도움이 된다.
// 변경사항을 저장할 보드를 전역변수로 선언한다.
int B[20][20];
// DFS를 이용하여 back tracking을 실시한다.
void dfs(int level) {
// 해당 문제에서 max depth는 5이다.
if (level == 5) {
// 가장 큰 블록을 저장 후 리턴한다.
int res = findMax();
ans = MAX(ans, res);
return;
}
// tmp[20][20]에 B[20][20]의 정보를 저장한다.
// tmp[20][20]에는 해당 depth에서의 보드 상태를 담고 있다.
copy(tmp,B);
// Move 수행 후 dfs()를 recursive하게 호출한다.
// 이를 통해 다음 depth로 확장을 실시한다.
for (int i=0; i<4; i++) {
if (i==0) moveLeft();
if (i==1) moveRight();
if (i==2) moveUp();
if (i==3) moveDown();
dfs(level + 1);
}
// Backtracking 실시
// 다시 이전 depth로 돌아오는 단계이다.
// 앞서 저장한 tmp[20][20]의 상태를 불러온다.
copy(B,tmp);
}
위와 같은 구조를 익혀두면 dfs를 이용하여 쉽고 효율적으로 backtracking을 할 수 있다.
풀이 방법
해당 문제를 푸는 데 가장 까다로웠던 것은 바로 숫자 블록의 이동이었다. 아래 간단한 몇가지 상황을 통해 어떻게 풀어야 하는지 살펴보자. 왼쪽으로 이동시키는 전제 하에 아래의 예시를 살펴보자.
(case 1)
(Q) 2 2 0 0
(A) 4 0 0 0
이는 매우 쉽다 그냥 왼쪽으로 밀면 된다.
(case 2)
(Q) 0 2 0 0
(A) 2 0 0 0
마찬가지로 그냥 왼쪽으로 밀면 된다.
(case 3)
(Q) 2 0 2 0
(A) 4 0 0 0
왼쪽으로 밀고 더해주면 된다.
(case 4)
(Q) 2 0 2 2
(1) 2 2 0 2
(2) 2 2 2 0
(3) 4 0 2 0
(4) 4 2 0 0
(A) 4 2 0 0
왼쪽의 수부터 연산을 수행하므로 왼쪽으로 밀고 더해준 후 또 왼쪽으로 밀어야 한다.
(case 5)
(Q) 2 0 2 4
(1) 2 2 0 4
(2) 2 2 4 0
(3) 4 0 4 0
(4) 4 4 0 0
(A) 4 4 0 0
마찬가지로 왼쪽으로 밀고 더해준 후 왼쪽으로 밀어야 한다.
정리해보면 아래와 같은 알고리즘으로 동작해야 한다.
1. 입력방향으로 밀어준다. (중간에 0인 블록이 있으면 안됨)
2. 숫자를 더해준다. (해당 작업을 실시하면 중간에 0인 블록이 생김)
3. 입력방향으로 밀어준다. (2번 이후 생긴 0인 블록을 밀어줌)
매우 까다롭고 생각해야 하는 케이스가 많은 문제였다. 이를 염두해두고 구현하면 다음과 같다.
void moveLeft() {
for (int i=0; i<n; i++) {
for (int j=0; j<n-1; j++) {
int flag = 0;
if (B[i][j] == 0) {
int k = j+1;
while (k <= n-1) {
if (B[i][k] != 0) {
flag = 1;
break;
}
k++;
}
if (flag == 1) {
B[i][j] = B[i][k];
B[i][k] = 0;
}
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<n-1; j++) {
if (B[i][j] == B[i][j+1]) {
B[i][j] *= 2;
B[i][j+1] = 0;
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<n-1; j++) {
int flag = 0;
if (B[i][j] == 0) {
int k = j+1;
while (k <= n-1) {
if (B[i][k] != 0) {
flag = 1;
break;
}
k++;
}
if (flag == 1) {
B[i][j] = B[i][k];
B[i][k] = 0;
}
}
}
}
}
코드
#include <stdio.h>
#include <iostream>
#include <stack>
#define MAX(a,b) (a>b?a:b)
using namespace std;
int n;
int ans = 0;
int board[20][20];
int B[20][20];
int findMax() {
int ret = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
ret = MAX(ret, B[i][j]);
}
}
return ret;
}
void moveLeft() {
for (int i=0; i<n; i++) {
for (int j=0; j<n-1; j++) {
int flag = 0;
if (B[i][j] == 0) {
int k = j+1;
while (k <= n-1) {
if (B[i][k] != 0) {
flag = 1;
break;
}
k++;
}
if (flag == 1) {
B[i][j] = B[i][k];
B[i][k] = 0;
}
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<n-1; j++) {
if (B[i][j] == B[i][j+1]) {
B[i][j] *= 2;
B[i][j+1] = 0;
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<n-1; j++) {
int flag = 0;
if (B[i][j] == 0) {
int k = j+1;
while (k <= n-1) {
if (B[i][k] != 0) {
flag = 1;
break;
}
k++;
}
if (flag == 1) {
B[i][j] = B[i][k];
B[i][k] = 0;
}
}
}
}
}
void moveRight() {
for (int i=0; i<n; i++) {
for (int j=n-1; j>0; j--) {
int flag = 0;
if (B[i][j] == 0) {
int k = j-1;
while (k >= 0) {
if (B[i][k] != 0) {
flag = 1;
break;
}
k--;
}
if (flag == 1) {
B[i][j] = B[i][k];
B[i][k] = 0;
}
}
}
}
for (int i=0; i<n; i++) {
for (int j=n-1; j>0; j--) {
if (B[i][j] == B[i][j-1]) {
B[i][j] *= 2;
B[i][j-1] = 0;
}
}
}
for (int i=0; i<n; i++) {
for (int j=n-1; j>0; j--) {
int flag = 0;
if (B[i][j] == 0) {
int k = j-1;
while (k >= 0) {
if (B[i][k] != 0) {
flag = 1;
break;
}
k--;
}
if (flag == 1) {
B[i][j] = B[i][k];
B[i][k] = 0;
}
}
}
}
}
void moveUp() {
for (int i=0; i<n-1; i++) {
for (int j=0; j<n; j++) {
int flag = 0;
if (B[i][j] == 0) {
int k = i+1;
while (k <= n-1) {
if (B[k][j] != 0) {
flag = 1;
break;
}
k++;
}
if (flag == 1) {
B[i][j] = B[k][j];
B[k][j] = 0;
}
}
}
}
for (int i=0; i<n-1; i++) {
for (int j=0; j<n; j++) {
if (B[i][j] == B[i+1][j]) {
B[i][j] *= 2;
B[i+1][j] = 0;
}
}
}
for (int i=0; i<n-1; i++) {
for (int j=0; j<n; j++) {
int flag = 0;
if (B[i][j] == 0) {
int k = i+1;
while (k <= n-1) {
if (B[k][j] != 0) {
flag = 1;
break;
}
k++;
}
if (flag == 1) {
B[i][j] = B[k][j];
B[k][j] = 0;
}
}
}
}
}
void moveDown() {
for (int i=n-1; i>0; i--) {
for (int j=0; j<n; j++) {
int flag = 0;
if (B[i][j] == 0) {
int k = i-1;
while (k >= 0) {
if (B[k][j] != 0) {
flag = 1;
break;
}
k--;
}
if (flag == 1) {
B[i][j] = B[k][j];
B[k][j] = 0;
}
}
}
}
for (int i=n-1; i>0; i--) {
for (int j=0; j<n; j++) {
if (B[i-1][j] == B[i][j]) {
B[i][j] *= 2;
B[i-1][j] = 0;
}
}
}
for (int i=n-1; i>0; i--) {
for (int j=0; j<n; j++) {
int flag = 0;
if (B[i][j] == 0) {
int k = i-1;
while (k >= 0) {
if (B[k][j] != 0) {
flag = 1;
break;
}
k--;
}
if (flag == 1) {
B[i][j] = B[k][j];
B[k][j] = 0;
}
}
}
}
}
void dfs(int level) {
if (level == 5) {
int res = findMax();
ans = MAX(ans, res);
return;
}
int tmp[20][20];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
tmp[i][j] = B[i][j];
}
}
for (int i=0; i<4; i++) {
if (i==0) {
moveLeft();
}
else if (i==1) {
moveRight();
}
else if (i==2) {
moveUp();
}
else if (i==3) {
moveDown();
}
dfs(level + 1);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
B[i][j] = tmp[i][j];
}
}
}
}
int main() {
cin >> n;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
cin >> board[i][j];
B[i][j] = board[i][j];
}
}
dfs(0);
cout << ans << "\n";
return 0;
}
정리
역시 map 문제는 풀이가 매우 까다롭다. 이런 문제들에 익숙해져서 쫄지 말고 풀어보자. 그리고 map전체의 상태가 한칸씩 변하는 것이 아니라 확확 변한다면 back tracking을 써볼 것을 생각하자.
댓글남기기