[백준 c++] 12100번 : 2048 (Easy)

문제 링크입니다.

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

12100번: 2048 (Easy)

 

풀이방법

최대 5번 이동시켰을 때의 최댓값을 구하는 문제이므로 dfs 알고리즘을 사용하여 해결합니다.

이 알고리즘에 대한 설명은 아래 링크를 참고해주세요.

https://dvpzeekke.tistory.com/37?category=887119

[c++] DFS(Depth First Search) 알고리즘

게임 '2048'을 구현하는 문제입니다.

이 문제를 구현할 때,

1. 상하좌우로 움직이기 (move 함수 생성)

2. 숫자 블록 합치기 (merge 함수 생성)

두 단계로 나눠서 생각하면 좋습니다.

 

상하좌우로 움직이는 것은 dfs 알고리즘을 사용합니다.

이 때, 백트래킹을 할 때 사용하기 위하여 temp라는 배열을 두었고 memcpy라는 함수를 활용했습니다.

move 함수에서는 각 행 또는 각 열을 queue에 넣는 작업을 수행합니다.

 

그 다음으로 숫자 블록을 합칠 때는 move 함수에서 만든 queue를 이용합니다.

queue에서 합쳐지거나 빠져나온 숫자 블록들은 board에 반영됩니다.

 

풀이

//
//  main.cpp
//  12100
//
//  Created by Jihye on 2020/04/15.
//  Copyright © 2020 Jihye Han. All rights reserved.
//

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int n = 0;
int ans = 0;
int board[20][20];

void assign(int index, int i, int j, int side, int front) {
    switch (side) {
        case 0: // 상
            board[index][j] = front; break;
        case 1: // 하
            board[n - index - 1][j] = front; break;
        case 2: // 좌
            board[i][index] = front; break;
        case 3: // 우
            board[i][n - index - 1] = front; break;
    }
}

void get(int i, int j, queue<int> &q) {
    if (board[i][j] != 0)
        q.push(board[i][j]);
    
    board[i][j] = 0;
}

void merge(int i, int j, int side, queue<int> q) {
    int index = 0;
    int front = 0;
    
    while (!q.empty()) {
        front = q.front();
        q.pop();
        
        if (q.empty()) { // q에 원소 남아있지 않을 때
            assign(index, i, j, side, front);
            return;
        }
        
        if (front == q.front()) {
            assign(index, i, j, side, front * 2);
            q.pop();
        } else {
            assign(index, i, j, side, front);
        }
        
        index += 1;
    }
}

void move(int side) {
    
    switch (side) {
        case 0: // 상
            for (int j = 0; j < n; j++) {
                queue<int> q;
                for (int i = 0; i < n; i++) {
                    get(i, j, q);
                }
                merge(0, j, side, q);
            }
            break;
            
        case 1: // 하
            for (int j = n - 1; j >= 0; j--) {
                queue<int> q;
                for (int i = n - 1; i >= 0; i--) {
                    get(i, j, q);
                }
                merge(0, j, side, q);
            }
            break;
            
        case 2: // 좌
            for (int i = 0; i < n; i++) {
                queue<int> q;
                for (int j = 0; j < n; j++) {
                    get(i, j, q);
                }
                merge(i, 0, side, q);
            }
            break;
            
        case 3: // 우
            for (int i = n - 1; i >= 0; i--) {
                queue<int> q;
                for (int j = n - 1; j >= 0; j--) {
                    get(i, j, q);
                }
                merge(i, 0, side, q);
            }
            break;
    }
}

int find() {
    int max = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] > max) max = board[i][j];
        }
    }
    
    return max;
}

void dfs(int count) {
    if (count == 5) {
        ans = max(ans, find());
        return;
    }
    
    int temp[20][20];
    memcpy(temp, board, sizeof(board));

    for (int i = 0; i < 4; i++) {
        move(i);
        dfs(count + 1);
        memcpy(board, temp, sizeof(temp));
    }
}

int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &board[i][j]);
        }
    }
    
    dfs(0);
    printf("%d\n", ans);
    
    return 0;
}