[백준/BOJ] 12100번 2048 (Easy)

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

삼성 역랑 테스트 기출 문제 : 시뮬레이션(구현)

 

DFS를 이용하여 해결할 수 있는 브루트포스/구현 문제입니다. 보드를 상하좌우 움직여 블록을 합치는 것을 구현하기 굉장히 어려운 문제였습니다. 

 

보드를 움직여 블록을 합치는 것은 다음과 같이 진행됩니다.

 

1. 보드를 기울이는 방향의 첫번째 인덱스부터 끝까지 블록의 값이 0이 아니라면 큐에 블록의 값을 넣어줍니다.

 

2. 현재 블록의 값에 0을 넣어줍니다. 

 

3. 다시 기울이는 방향의 첫번째 인덱스부터 끝까지 큐의 값과 비교를 합니다.

 

• 만약 현재 보드에 있는 블록의 값이 0이라면, 큐의 front() 값을 현재 블록에 대입
• 만약 현재 보드에 있는 블록의 값과 큐의 front() 값이 같다면, 현재 블록에 2배를 하고 인덱스 증가
• 만약 현재 보드에 있는 블록의 값과 큐의 front() 값이 다르면, 인덱스 증가 후 현재 블록에 큐의 front() 값을 대입 

#include <iostream>
#include <queue>
using namespace std;

int n,res=-2147000000;
int board[21][21];

void move(int dir) {
    queue<int> q;
    switch(dir) {
            
        // 왼쪽
        case 0:
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    if(board[i][j]>0) q.push(board[i][j]);
                    board[i][j]=0;
                }
                int idx=0;
                while(!q.empty()) {
                    int value=q.front();
                    q.pop();
                    if(board[i][idx]==0) {
                        board[i][idx]=value;
                    } else if(board[i][idx]==value) {
                        board[i][idx]*=2;
                        idx++;
                    } else {
                        idx++;
                        board[i][idx]=value;
                    }
                }
            }
            break;
            
        // 오른쪽
        case 1:
            for(int i=0;i<n;i++) {
                for(int j=n-1;j>=0;j--) {
                    if(board[i][j]>0) q.push(board[i][j]);
                    board[i][j]=0;
                }
                int idx=n-1;
                while(!q.empty()) {
                    int value=q.front();
                    q.pop();
                    if(board[i][idx]==0) {
                        board[i][idx]=value;
                    } else if(board[i][idx]==value) {
                        board[i][idx]*=2;
                        idx--;
                    } else {
                        idx--;
                        board[i][idx]=value;
                    }
                }
            }
            break;
            
        // 위
        case 2:
            for(int j=0;j<n;j++) {
                for(int i=0;i<n;i++) {
                    if(board[i][j]>0) q.push(board[i][j]);
                    board[i][j]=0;
                }
                int idx=0;
                while(!q.empty()) {
                    int value=q.front();
                    q.pop();
                    if(board[idx][j]==0) {
                        board[idx][j]=value;
                    } else if(board[idx][j]==value) {
                        board[idx][j]*=2;
                        idx++;
                    } else {
                        idx++;
                        board[idx][j]=value;
                    }
                }
            }
            break;
            
        // 아래
        case 3:
            for(int j=0;j<n;j++) {
                for(int i=n-1;i>=0;i--) {
                    if(board[i][j]>0) q.push(board[i][j]);
                    board[i][j]=0;
                }
                int idx=n-1;
                while(!q.empty()) {
                    int value=q.front();
                    q.pop();
                    if(board[idx][j]==0) {
                        board[idx][j]=value;
                    } else if(board[idx][j]==value) {
                        board[idx][j]*=2;
                        idx--;
                    } else {
                        idx--;
                        board[idx][j]=value;
                    }
                }
            }
            break;
    }
}

void DFS(int L) {
    if(L==5) {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(res>=board[i][j]) continue;
                res=max(res,board[i][j]);
            }
        }
        return;
    } else {
    	// 원래 보드 위치의 저장 
        int copy[21][21];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                copy[i][j]=board[i][j];
            }
        }
        for(int i=0;i<4;i++) {
            move(i);
            DFS(L+1);
            // 이동 후 위치 다시 원상태  
            for(int j=0;j<n;j++) {
                for(int k=0;k<n;k++) {
                    board[j][k]=copy[j][k];
                }
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            cin>>board[i][j];
        }
    }
    DFS(0); // 보드 이동 수 
    cout<<res;
}

 

위처럼 보드를 상, 하, 좌, 우로 기울였을 때 블록이 이동하는 경우를 구현하는 것도 매우 훌륭한 풀이이지만 구현이 까다롭고 코드가 길어진다는 단점이 있습니다. 바킹독님의 강의를 들으면서 이러한 단점을 해결하기 위한 좋은 풀이를 알게 되었는데, 바로 보드 자체를 회전하는 방법입니다.

 

아래의 코드에서 방향 dir은 4의 나머지로 결정되므로 항상 0, 1, 2, 3의 값을 갖고 moveBlock 함수로 들어오게 된다. 이 dir이 값에 따라 보드를 회전해주는 것입니다. 예를들어 다음과 같습니다.

 

dir == 0 : roate 함수가 실행되지 않는다. => 회전 X

dir == 1 : roate 함수가 1번 실행된다. => 90도 회전

dir == 2 : roate 함수가 2번 실행된다. => 180도 회전

dir == 3 : roate 함수가 3번 실행된다. => 270도 회전

 

이러한 방법을 이용하면 블록이 이동해서 합쳐지는 코드를 상, 하, 좌, 우 모두 구현할 필요 없이 하나만 구현해도 답을 도출해낼 수 있습니다.

 

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 25;

int map[MAX][MAX];
int cp[MAX][MAX];
int n, answer;

// 게임판을 회전하는 함수 
void rotate() {
	int tmp[MAX][MAX];
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			tmp[i][j] = cp[i][j];
		}
	}
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cp[i][j] = tmp[n - j - 1][i];
		}
	}
}

// 블록의 최대값을 구하는 함수  
int getMaxBlock() {
    int res = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            res = max(res, cp[i][j]);
        }
    }
    return res;
}

// 지정된 방향으로 블록을 기울이는 함수  
void moveBlock(int dir) {
    while(dir--) rotate(); // 게임판 회전
    queue<int> q;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(cp[i][j] > 0) q.push(cp[i][j]);
            cp[i][j] = 0;
        }
        
        
        int idx = 0;    
        while(!q.empty()) {
            int val = q.front();
            q.pop();
            
            if(cp[i][idx] == 0) cp[i][idx] = val;
            else if(cp[i][idx] == val) cp[i][idx++] *= 2;
            else cp[i][++idx] = val;
        }
    }
}

// 경우의 수마다 게임판을 매번 복사/초기화 하는 함수  
void copyAndInit() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cp[i][j] = map[i][j];
        }
    }
}
 
// 게임판을 움직일 방향을 정하는 함수  
void getDirection() {
    for(int d = 0; d < (1 << (2 * 5)); d++) {
        copyAndInit();
        int tmp = d;
        for(int i = 0; i < 5; i++) {
            int dir = tmp % 4;
            tmp /= 4;
            moveBlock(dir);
        }
        answer = max(answer, getMaxBlock());
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin>>map[i][j];
        }
    }
    
    getDirection();
    cout<<answer;
}