[BOJ] 2048. Easy.py.cpp (brute force)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

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

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

2048 게임을 모티브로 만든 문제이다.

4가지 방향으로 최대 5번까지 이동할 수 있다고 하였으므로,

총 4^5의 경우의 수가 발생할 것이다.

1. 최대 5번까지 상하좌우로 이동하는 BFS 함수

2. 상하좌우로 이동하였을 때 board에서 일어나는 동작들을 수행하는 함수가 필요할 것 같다.

처음 생각했을 때는 상하좌우에 따른 동작을 하는 함수를 다 만들려고 했었는데..

동작은 한 곳에서 하고 방향을 돌려주는 방법이 훨씬 효율적이라고 알게 되었다.

하긴.. 방향만 다를 뿐 실질적인 동작은 같은데 따로따로 구현해줄 필요는 없을 것 같다.

구현하는데 드는 시간도 그렇고..

역쉬..!

1. DFS()로 가능한 경우의 수 탐색

2. 숫자 합치기

3. 숫자가 합쳐졌다면 DFS()를 다시 호출

4. 변화가 없다면 90도 회전

#. Python

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

from copy import deepcopy   N = int(input()) Board = [list(map(int, input().split())) for _ in range(N)]   def Rotate(N, B):     new_brd = deepcopy(B)     for i in range(N):         for j in range(N):             new_brd[j][N-i-1] = B[i][j]     return new_brd   def Combine(N, B):     tmp = []     for lst in B:         new_lst = [i for i in lst if i]         for i in range(1, len(new_lst)):             if new_lst[i-1] == new_lst[i]:                 new_lst[i - 1] *= 2                 new_lst[i] = 0         new_lst = [i for i in new_lst if i]         tmp += [new_lst + [0] * (N - len(new_lst))]     return tmp   def CombineLst(N, lst):     new_lst = [i for i in lst if i]     for i in range(1, len(new_lst)):         if new_lst[i-1] == new_lst[i]:             new_lst[i - 1] *= 2             new_lst[i] = 0     new_lst = [i for i in new_lst if i]     return new_lst + [0] * (N - len(new_lst))     def DFS(N, B, cnt):     rst = max([max(i) for i in B])     if cnt == 0:         return rst     for _ in range(4):         tmp = Combine(N, B)         # tmp = [CombineLst(N, i) for i in B]         if tmp != B:             rst = max(rst, DFS(N, tmp, cnt-1))         B = Rotate(N, B)     return rst   print(DFS(N, Board, 5)) Colored by Color Scripter

cs

line 35~45) Board를 상하좌우로 이동시키는 함수

line 36) Board에서 가장 큰 수를 rst에 저장

line 37) cnt가 0일 경우, 재귀함수 종료

line 39~44) Board를 상하좌우로 이동시켜본다.

line 40) Board를 안 원소들을 이동시키는 Combine 함수 호출

line 42) 만일 Board를 이동시킨 결과가 기존 Board와 다를 경우, (내용이 수정되었을 경우)

line 43) Board를 회전시키지 않고 같은 방향으로 계속 이동

line 44) Board를 90도 회전

line 13~23)  Board를 안 원소들을 이동시키는 Combine 함수

line 15~22) 한 줄씩 작업

line 16) 해당 라인에서 0이 아닌 수만 newList에 저장

line 17~20) 앞에 자신과 같은 숫자가 있을 경우 

line 19) 자신의 앞은 2배를 해주고 자신은 0으로

line 21) 위 결과에서 다시 0이 아닌 수만 newList에 저장

line 22) Board의 크기에 맞게 newList의 크기를 조정

line 6~11) Board를 90도 회전시키는 함수

line 7) deepcopy를 사용하여 내용만 복사

line 8~10) Board를 90도 회전

어려운 문제에 속한다고는 했는데..

정말 어려웠다ㅠㅠ

내일 C++로 다시 풀어봐야지..

#. C++

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
int N, res = -21470000;
vector<vector<int>> Board;
 
vector<vector<int> >  Rotate(vector<vector<int> > B)
{
    int i, j;
 
    vector<vector<int> > NB(N, vector<int>(N, 0));
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            NB[j][N - i - 1] = B[i][j];
        }
    }
 
    return NB;
}
 
vector<int> Combine(vector<int> lst)
{
    int i;
    vector<int> vt1, vt2;
    // 0이 아닌 숫자만 모아서
    for (auto i : lst)
        if (i)
            vt1.push_back(i);
 
    // 합치기
    for (i = 1; i < vt1.size(); i++)
    {
        if (vt1[i - 1] == vt1[i])
        {
            vt1[i - 1] *= 2;
            vt1[i] = 0;
        }
    }
 
    // 다시 0이 아닌 숫자만 모아서
    for (auto i : vt1)
        if (i)
            vt2.push_back(i);
 
    for (i = 0; vt2.size() != N; i++)
        vt2.push_back(0);
 
    return vt2;
}
 
int DFS(vector<vector<int> > B, int cnt)
{
    int i, j;
 
    // Board에서 가장 큰 수 찾기
    for (i = 0; i < N * N; i++)
        res = max(res, B[i/N][i%N]);
 
    if (!cnt)
        return res;
    
    for (i = 0; i < 4; i++)
    {
        vector<vector<int> > X(N);
        for (j = 0; j < N; j++) 
            X[j] = Combine(B[j]);
 
        if (X != B)
            res = max(res, DFS(X, cnt - 1));
        
        B = Rotate(B);
    }
    
    return res;
}
 
int main(void)
{
    int i, j;
 
    scanf("%d", &N);
    Board.resize(N, vector<int>(N, 0));
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            scanf("%d", &Board[i][j]);
 
    printf("%d\n", DFS(Board, 5));
 
    return 0;
}

많이 참고하면서 해결했는데, 정말 배운게 많았다..

line 86) 전역변수로 선언한 2차원 vector Board를 resize해주면서 0으로 초기화

     * 배열보다 vector를 활용하는게 탐색에서도 정말 유용할 것 같다.)

line 91) DFS()에 Board와 최대 이동 횟수를  넘겨준다.

line 55~79) Board를 다양한 경우의 수로 이동시키기 위한 함수

line 60) Board에서 가장 큰 수를 찾는다.
          이차원 배열을 사용하지 않고 index번호로 배열을 참조하는 방법이 흥미롭다.

line 63) 5번의 이동 횟수를 모두 사용했을 경우 return

line 66~76) 상하좌우 네 방향으로 board를 이동시켜보기 위해 4번 반복

line 68) temp 이차원 벡터를 생성

line 69) 매개변수로 들어온 Board를 이동시켜주는데, 한 줄씩 이동시켜준다.

* python에서 list = list2 가 동작하는 것 처럼 c++에서 vector끼리 복사가 성립하는지 알게 되었다..

line 72) 결과 Board와 기존 Board가 다를 경우 계속 같은 방향으로 이동시켜볼 수 있다.

DFS()의 return값은 res이므로 최대 res를 구해주고, DFS()에는 결과 Board를 넣어준다.

DFS()를 호출하는 것은 이동 동작을 수행하는 것이므로 count를 줄여줘야 한다.

line 75) 결과 Board와 기존 Board가 같을 경우는 이동 동작을 수행하여도 변화가 없다는 것이다.

그러므로 다른 방향으로 이동시켜보기위해 90도 회전시켜준다.

90씩 회전시키는 것은 다른 방향으로 이동시키는 것과 같은 효과를 볼 수 있다.

line 25~53) Board 원소들을 이동시키는 함수

line 28) temp vector를 생성

line 30~32) 매개변수로 받은 board의 한 줄에서 0이 아닌 숫자를 vector에 담아준다.

* vector의 원소값으로 반복문을 동작시키는 auto도 유용하게 사용될 수 있을 것 같다.

line 35~42) 이전 index의 값과 현재 index의 값이 같을 경우 합쳐줘야 한다.

(이 부분은 글로 설명하기가 어렵구만)

line 45~47) 합쳐진 값을 저장한 vector에서 또 다시 0이 아닌 수만 vector2에 담아준다.

( 2 2 2 2 를 합치고 난 결과는 4 0 4 0 이 되므로, 4 4 0 0 이 되도록 다시 설정해주어야 한다.)

line 49~50) 이제 {4, 4} 를 담았으니 남은 공간은 0으로 채워줘야 한다.

line 9~23) Board를 돌려주는 함수

line 13) temp Board 생성

line 14~20) Board를 90도 돌려주는 핵심 코드

line 18) 회전 알고리즘인 NB[j][N-i-1] = B[i][j] 는 외워주면 좋을 것 같다.

이와 같이 복잡한 탐색 문제를 많이 풀어봐야 할 것 같다.

골드2 문제인데 나에겐 아직 많이 어렵다ㅠㅠ