백준(boj) 12100_2048 (파이썬, c++)

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

풀이

---

상하좌우 4방향으로 이동을 할 수 있는데, 같은 값을 갖는 두 블록이 충돌하면 두 블록이 하나로 합친다. 단, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐지지 않도록 한다. st=[] (스택의 역할을)라는 리스트와 idx(index의 역할을)라는 변수를 사용해서 구현했다. 비교하려는 idx값이 없으면 => 이전에 추가된 값이 없으므로 값만 추가해준다. idx는 그대로 둔다. 비교하려는 idx값이 있으면 => 이전에 추가된 값과 비교하고 idx를 1 올려준다. 만약 비교값이 같으면 합쳐지는 것이므로 두 배 해주고, 다르면 새로운 값을 추가해준다. 그렇게 최댓값을 구해야 하므로 완전 탐색 해준다. solve() 함수를 이용해서 완전 탐색 해주었다. (문제에 최대 5번 이동시키라 했으므로 base case: cnt==5)

python3

from sys import*
from collections import*
input = stdin.readline
def cal(x, y, dx, dy):
    global a, res
    st=[]; idx=0
    nx, ny = x, y
    for i in range(n):
        if not a[nx][ny]:
            nx, ny = nx+dx, ny+dy
            continue
        if len(st) <= idx:
            st.append(a[nx][ny])
        else:
            if st[idx] == a[nx][ny]:
                st[idx] *= 2
                res = max(res, st[idx])
            else:
                st.append(a[nx][ny])
            idx+=1
        nx, ny = nx+dx, ny+dy
    nx, ny = x, y
    st_len = len(st)
    for i in range(n):
        if st_len > i: a[nx][ny] = st[i]
        else: a[nx][ny] = 0
        nx, ny = nx+dx, ny+dy
​
def move(d):
    for i in range(n):
        if d==0: cal(i, 0, 0, 1)       #L
        elif d==1: cal(0, i, 1, 0)     #U
        elif d==2: cal(i, n-1, 0, -1)  #R
        elif d==3: cal(n-1, i, -1, 0)  #D
        
def solve(cnt):
    global a
    if cnt == 5: return
    b = [x[:] for x in a]
    for i in range(4):
        move(i)
        solve(cnt+1)
        a = [x[:] for x in b]
    return    
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
res=-987654321
for i in range(n):
    res = max(res, max(a[i]))
solve(0)
print(res)

C++

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>     //memcpy
using namespace std;
int n,res;
const int SIZE = 20;
int a[SIZE][SIZE];
​
void move(int d){
    if(d==0 || d==3){
        for(int i=0; i<n; i++){
            vector<int> v;
            int idx = 0;
            for(int j=0; j<n; j++){
                int val = d==0 ? a[j][i] : a[i][j];
                if(val == 0) continue;
                if(idx >= v.size()) v.push_back(val);
                else{
                    if(v[idx]== val){
                        v[idx] *= 2;
                        res = max(res, v[idx]);
                    }
                    else{
                        v.push_back(val);
                    }
                    idx+=1;
                }
            }
            for(int j=0; j<v.size(); j++){
                if(d==0) a[j][i] = v[j];
                else a[i][j] = v[j];
            }
            for(int j=v.size(); j<n; j++){
                if(d==0) a[j][i] = 0;
                else a[i][j] = 0;
            }
        }
    }
    else if(d==1 || d==2){
        for(int i=0; i<n; i++){
            vector<int> v;
            int idx = 0;
            for(int j=n-1; j>-1; j--){
                int val = d==2 ? a[j][i] : a[i][j];
                if(val ==0) continue;
                if(idx >= v.size()) v.push_back(val);
                else{
                    if(v[idx]==val){
                        v[idx] *= 2;
                        res = max(res, v[idx]);
                    }
                    else{
                        v.push_back(val);
                    }
                    idx+=1;
                }
            }
            for(int j=0; j<v.size(); j++){
                if(d==2) a[(n-j-1)][i] = v[j];
                else a[i][(n-j-1)] = v[j];
            }
            for(int j=v.size(); j<n; j++){
                if(d==2) a[(n-j-1)][i] = 0;
                else a[i][(n-j-1)] = 0;
            }
        }
    }
}
void solve(int cnt){
    int b[SIZE][SIZE];
    if(cnt == 5) return;
    memcpy(b, a, sizeof(a));
    for(int i=0; i<4; i++){
        move(i);
        solve(cnt+1);
        memcpy(a, b, sizeof(b));
    }
    return;
}
int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
            scanf("%d", &a[i][j]);
            res = max(res, a[i][j]);
        }
    solve(0);
    printf("%d", res);
    return 0;
}

고찰

---

move() 함수 반절 똑 잘라서 함수로 구현하면 코드가 훨씬 이쁠거같다.

좀 더 이쁘게 다시 짰다. 전과의 비교를 위해 c++ 코드는 이전 그대로 뒀다.