[BOJ] 12100. 2048(easy)

[문제]

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

12100번: 2048 (Easy)

[풀이]

 

12100

맞았습니다!!

1988

8

C++14 / 수정

2184

2일 전

 

1) 인덱스에 주의를 기울여야 한다. 

 

2) 상하 / 좌우를 모두 왼-> 오른쪽으로 이동하도록 만들어야 한다. (이동을 쉽게 하기 위해)

 

2	2	2
4	4	4
8	8	8

 

상하

2	4	8
2	4	8
2	4	8

 

 

좌우

2	2	2
4	4	4
8	8	8

 

3) 오른쪽, 아래의 경우에는 뒷 인덱스에서 앞쪽 인덱스로 블록을 이동하거나 합쳐야 하기 때문에 거꾸로 만들어줘야 한다. (오른쪽으로 밀거니까)

=> 이를 위해서 vector의 begin(), end() iterator 를 사용할 수 있도록 블록의 값들을 list라는 vector에 담아두었고, 

algorithm 라이브러리의 reverse 메소드를 사용하여 뒤집어줬다. 

 

4) 같은 수가 적힌 두 블록이 만나면 하나로 합쳐져야 한다. 

(단, 한 번 합쳐진 블록은 다시 합쳐지지 않는다.)

=> 다시 합쳐지지 않게 하기 위해 (i, j) + (i, j+1) 이 합쳐졌다면 (j+2)부터 비교할 수 있도록 해주었다. 

=> 이동한 블록들은 combine_list 에 넣어서 보관한다. 

 

5) 합쳐진 블록들을 다시 맵에 넣기 위해 (기존 맵의 보존을 위해 prev라는 변수로 기존 맵을 파라미터로 넘겨주었고, c_map 이라는 이차원 배열을 사용하여 새롭게 이동한 블록들을 넣어주었다.)

상 -> (j, i )

하 -> (n-j-1, i) (아까 리버스 해줌)

좌 -> (i , j)

우 -> ( i , n-j-1 )(아까 리버스 해줌)

 

이렇게 인덱스를 지정해서 넣어준다. 

 

6) 게임은 총 5번 이동이 가능하기 때문에 dfs를 사용해서 상하좌우 각 방향으로 이동하도록 했다. 

이때, 방향도 같이 파라미터로 넘겨주었다. 

게임이 종료되면 가장 큰 값을 비교해서 출력한다. 

---

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int n, ans = 0;
 
void maxBlockNum(int (*map)[21])
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            if (ans < map[i][j])
                ans = map[i][j];
    }
}
void dfs(int cnt, int dir, int (*map)[21])
{
    if (cnt == 5)
    {
        maxBlockNum(map);
        return;
    }
 
    int c_map[21][21];
    memset(c_map, 0, sizeof(c_map)); //합친 블록들을 옮길 맵을 생성(dfs 호출 시 넘긴다.) -> 본래의 map과 구별되어 사용
 
    vector<int> blocks, combine;
    //이동을 위해 임시 저장 배열, 합친 블록을 저장하는 배열
 
    for (int i = 0; i < n; i++)
    {
        blocks.clear();
        combine.clear(); //행이나 열이 달라질 때마다 초기화
 
        for (int j = 0; j < n; j++)
        {
            if (dir == 0 || dir == 1)
            {
                //상하
                if (map[j][i])
                    //합칠 때 0은 빈칸 취급
                    blocks.push_back(map[j][i]);
            }
            else {
                if (map[i][j]) blocks.push_back(map[i][j]);
            }
        }
 
        //오른쪽과 아래 방향인 경우 인데스가 작은 것-> 큰 것으로 합쳐지기 때문에 
        //뒤집어서 큰 것이 작은 인덱스 방향으로 합쳐지게끔 한다. 
        if (dir == 1 || dir == 3) reverse(blocks.begin(), blocks.end());
 
        for (int j = 0; j < blocks.size(); j++) {
            //합치는 작업 
            //중복으로 합치는 과정은 만약 지금 인덱스와 다음 인덱스의 값이 같을 경우 2칸을 뛰어넘기 때문에 고려하지 않아도 된다. 
            if (j != blocks.size()-1 && blocks[j] == blocks[j+1]) {
                combine.push_back(blocks[j]*2); //같은 숫자일 때 
                j++;
            }
            else combine.push_back(blocks[j]);
        }
 
        //c_map에 옮기기 
        //오른쪽과 아래는 리스트를 뒤집은 상태이기 때문에 인덱스 고려해야한다. 
        for(int j = 0; j < combine.size(); j++) {
            if (dir == 0) 
                c_map[j][i] = combine[j];
            else if (dir == 1) 
                c_map[n-j-1][i] = combine[j];
            else if (dir == 2) 
                c_map[i][j] = combine[j];
            else
                c_map[i][n-j-1] = combine[j];
            
        }
 
    }//for i
 
    maxBlockNum(c_map);
 
    for (int i = 0; i < 4; i++) {
        //5번이 될 때까지 회전 
        dfs(cnt+1, i, c_map);
    }
 
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    int map[21][21];
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    } //input
 
    for (int i = 0; i < 4; i++)
    {
        dfs(0, i, map);
    }
    cout << ans << '\n';
    return 0;
}