[백준] 12100번 2048 (Easy) C++

https://www.acmicpc.net/problem/12100

2048 (Easy) 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	33905	8594	4909	23.508%

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다.

<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>	<그림 15>

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

예제 입력 1 

3
2 2 2
4 4 4
8 8 8

예제 출력 1 

16

처음에 동서남북 방향 각각 Case를 걸어서 하면 코드가 너무 길어질 것 같은데 라고 생각하면서 한숨을 쉬며 시작했던 문제다. 

결국 처음에 코딩할 때 매우 더러운 코드가 결과적으로 나왔고, 계속 틀린 답이 나오게 되었다...ㅋㅋㅋㅋ

다른 사람의 코드도 이렇게 긴가? 싶어서 힐끗 찾아봤는데 짧다.....내 생각이 짧듯이.....

그래서 DFS만 놔두고 이동하는 로직을 오늘 카페와서 새로 작성했더니 깔끔해졌다!!!!!

• 풀이방법

1. 우선 방향(dir)을 설정한다. 나는 계산 편의를 위해 동(0), 남(1), 서(2), 북(3) 으로 index를 설정하였다.
2. 4방향을 반복하며 DFS를 수행하면서 블록을 해당 방향으로 이동하는 로직을 작성한다. (아래 그림 참조)
3. 해당 방향에서 부터 0이 아닌 숫자를 Queue에 담는다.
4. While문을 돌면서 Queue(=q)에 담긴 것들을 하나씩 꺼내며 Vector(=data)에 넣어준다.
1. q.front() - 변수(cur)에 저장한 후 pop()
2. pop을 했는데 q.empty()==true? data에 삽입 후 break;
3. pop을 했는데 q.empty()==false? 한 번더 q.front() - 변수(next)와 처음 꺼낸 값(cur)과 비교
1.  같다? pop 후 data에 cur * 2값을 삽입 (최대값==answer 갱신)
2.  다르다? data에 cur 값을 삽입
5. data의 크기가 N이 될 때까지 0을 넣어준다.
6. data의 값을 다시 방향에 맞게 해당 행(board[j][i]) or 열(board[i][j])에 넣어준다.
7. answer값 출력하면 정답!

그림1

※ 유의사항

• DFS를 재귀로 호출하기 전에 board를 copy한 새로운 board를 넘겨주어야 한다. 원본이 변경되기 때문
• DFS함수의 매개변수로 board를 받을 때 &을 붙여주는 것이 좋다. 붙여주지 않으면 배열의 복사가 일어나기 때문
  

삼성 A형 기출문제들은 알고리즘 쓰는 건 간편한데 구현이 너무 빡센 것 같다 ㅠㅠ(남들에겐 쉬울지 모르지만...)

• 소스코드

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int N;
int answer = 0;
 
void moveTo(vector<vector<int>>& board, int dir) {
    // 동(0), 남(1)은 index가 배열의 끝부터 시작
    // 서(2), 북(3)은 index가 배열의 처음부터 시작
    int starti = dir < 2 ? N - 1 : 0,
        endi = dir < 2 ? -1 : N,
        op = dir < 2 ? -1 : 1;
    for (int j = 0; j < N; j++) {
        queue<int> q; // 행or열 중 0이 아닌 숫자들을 담을 Queue
        for (int i = starti; i != endi; i += op) {
            if (dir % 2 == 0 && board[j][i]) // 동,서
                q.push(board[j][i]);
            else if (dir % 2 == 1 && board[i][j]) // 남,북
                q.push(board[i][j]);
        }
 
        // 합쳐진 후 다시 board에 넣을 값이 담길 벡터
        vector<int> data; 
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            if (q.empty()) {
                data.push_back(cur);
                break;
            }
            int next = q.front();
            if (cur == next) { // 현재값과 다음값이 같으면 2를 곱한 값 배열에 삽입
                data.push_back(cur * 2);
                // 최댓값(answer) 계산
                answer = answer < cur * 2 ? cur * 2 : answer;
                q.pop();
            }
            else
                data.push_back(cur);
        }
 
        // 벡터사이즈가 N이 되게끔 0 개수 맞춰주기
        while (data.size() != N) 
            data.push_back(0);
 
        // 계산한 값 다시 넣어주기
        int idx = 0;
        for (int i = starti; i != endi; i += op) { 
            if (dir % 2 == 0) // 동, 서
                board[j][i] = data[idx++];
            else if (dir % 2 == 1) // 남, 북
                board[i][j] = data[idx++];
        }
    }
}
void dfs(int count, vector<vector<int>>& board) {
    if (count >= 5)
        return;
 
    for (int dir = 0; dir < 4; dir++) { // 0:동, 1:남, 2:서, 3:북
        vector<vector<int>> c_board;
        c_board.assign(board.begin(), board.end());
        moveTo(c_board, dir);
        dfs(count + 1, c_board);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> N;
    vector<vector<int>> board(N, vector<int>(N, 0));
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (answer < board[i][j] && board[i][j] != 0)
                answer = board[i][j];
        }
    }
    dfs(0, board);
    cout << answer << endl;
    return 0;
}

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이	제출한 시간
19910308	myabc17	12100	맞았습니다!!	2120 KB	20 ms	C++14 / 수정	1893