BOJ : 12100 2048(Easy)

문제 : https://www.acmicpc.net/problem/3190

2016년 삼성 하반기 공채 SW 역량테스트 오전 문제

째로탈출과 같이 나온 오전 문제. 

한 때 인기몰이를 했던 2048 게임의 축소판이다.

이 문제는 최대 이동횟수가 5이기에 DFS나 BFS 두 가지 방법으로 모두 해결가능하다.

하지만 한 쪽으로 기울일 때 숫자가 합쳐지는 과정을 어떻게 구현하느냐가 문제!

상하좌우를 각각 짜서 코드 가독성이 매우 안좋음

나는 한 쪽으로 치우쳐지면서 숫자가 합쳐지는 것을 vector로 짰다. 

0(빈공간)을 제외한 숫자를 벡터에 받고 v[k]와 v[k+1]을 비교한 후 같으면 v[k]*2, v[k+1]=0으로 만들어주고 다시 숫자판에 초기화해주었음.

포스팅하기 민망한 코드이지만 필요할 수도 있는 사람을 위해서 올림ㅠㅠ

2016년 삼성 하반기 공채 SW 역량테스트 문제

12100 2048(Easy) / 해설 오전

3190 뱀  오후

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int N,ans=0,cnt=1;
vector<vector<int>> m;
queue<vector<vector<int>>> q;
 
 
void print(vector<vector<int>> map){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
int main(){
    scanf("%d",&N);
    m.resize(N*N);
    for(int i=0;i<N;i++){
        for(int j=0,n;j<N;j++){
            scanf("%d",&n);
            m[i].push_back(n);
        }
    }
    ans=m[0][0];
    q.push(m);
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            
            vector<vector<int>> t = q.front();
            q.pop();
            
            //right
            vector<vector<int>> tt;
            tt.resize(N*N);
            for(int r=0;r<N;r++){
                
                for(int rr=0;rr<N;rr++)
                    for(int cc=0;cc<N;cc++)
                        tt[rr].push_back(0);
                
                vector<int> v;
                v.resize(N);
                for(int c=N-1;c>=0;c--)
                    if(t[r][c] !=0) v.push_back(t[r][c]);
                
                for(int k=0;k<v.size();k++){
                    if(k==v.size()-1) {
                        if(ans < v[k]) ans=v[k];
                        continue;
                    }
                    if(v[k]==v[k+1]) {
                        v[k] += v[k+1];
                        if(ans < v[k]) ans = v[k];
                        v[k+1] = 0;
                    }
                }
                
                for(int k=0,l=N-1;k<v.size();k++){
                    if(v[k] !=0){
                        tt[r][l--] = v[k];
                    }
                }
            }
            q.push(tt);
            
            
            //left
            tt.clear();
            tt.resize(N*N);
            for(int r=0;r<N;r++){
                
                for(int rr=0;rr<N;rr++)
                    for(int cc=0;cc<N;cc++)
                        tt[rr].push_back(0);
                
                
                vector<int> v;
                v.resize(N);
                for(int c=0;c<N;c++)
                    if(t[r][c] !=0) v.push_back(t[r][c]);
                
                for(int k=0;k<v.size();k++){
                    if(k==v.size()-1) {
                        if(ans < v[k]) ans=v[k];
                        continue;
                    }
                    if(v[k]==v[k+1]) {
                        v[k] += v[k+1];
                        if(ans < v[k]) ans = v[k];
                        v[k+1] = 0;
                    }
                }
                
                for(int k=0,l=0;k<v.size();k++){
                    if(v[k] !=0){
                        tt[r][l++] = v[k];
                    }
                }
            }
            
            q.push(tt);
            
            //up
            tt.clear();
            tt.resize(N*N);
            for(int c=0;c<N;c++){
                
                for(int rr=0;rr<N;rr++)
                    for(int cc=0;cc<N;cc++)
                        tt[rr].push_back(0);
                
                
                vector<int> v;
                v.resize(N);
                for(int r=0;r<N;r++)
                    if(t[r][c] !=0) v.push_back(t[r][c]);
                
                
                
                for(int k=0;k<v.size();k++){
                    if(k==v.size()-1) {
                        if(ans < v[k]) ans=v[k];
                        continue;
                    }
                    if(v[k]==v[k+1]) {
                        v[k] += v[k+1];
                        if(ans < v[k]) ans = v[k];
                        v[k+1] = 0;
                    }
                }
                
                for(int k=0,l=0;k<v.size();k++){
                    if(v[k] !=0){
                        tt[l++][c] = v[k];
                    }
                }
                
                
                
            }
            q.push(tt);
            
            //down
            tt.clear();
            tt.resize(N*N);
            for(int c=0;c<N;c++){
                
                for(int rr=0;rr<N;rr++)
                    for(int cc=0;cc<N;cc++)
                        tt[rr].push_back(0);
                
                vector<int> v;
                v.resize(N);
                for(int r=N-1;r>=0;r--)
                    if(t[r][c] !=0) v.push_back(t[r][c]);
                
                for(int k=0;k<v.size();k++){
                    if(k==v.size()-1) {
                        if(ans < v[k]) ans=v[k];
                        continue;
                    }
                    if(v[k]==v[k+1]) {
                        v[k] += v[k+1];
                        if(ans < v[k]) ans = v[k];
                        v[k+1] = 0;
                    }
                }
                
                for(int k=0,l=N-1;k<v.size();k++){
                    if(v[k] !=0){
                        tt[l--][c] = v[k];
                    }
                }
                
            }
            q.push(tt);
            
        }
        cnt++;
        if(cnt>5) break;
    }
    printf("%d\n",ans);
}