[백준] 12100 - 2048(Easy) by C++

Jewon's report·2023년 3월 21일
0

c++ / 알고리즘

목록 보기
3/5

❗️ BFS -> DFS

bfs로 풀려다가 큐에 너무 많이 넣어서 메모리 초과가 나왔다.

그래서 dfs로 선회해서 문제풀었음.

다시생각해보니 굳이 스택에 넣어놓을 필요가 없다고 생각.

그냥 5번 움직이는 모든 경우중에서 최대만 걸러오면 되기 때문에.

최댓값 비교를 상,하,좌,우 움직임 에서 합쳐지는 행동이 발생할때 마다 비교.

🤬 4% 지옥

4%에서 진짜 몇십번 틀렸는데, Left 과정의 while문에서 ==0 이거 안써서 계속 틀렸던 것임...



깊이우선탐색
--> 0있는 칸 없이 블럭들이 모두 움직이려는 방향으로 모이게 한다.
--> 옆 블록끼리 같은 수 인지 비교

ex)  RIGHT 로 합치려는 경우
004        004       004
202   -->      022  -->      004
204        024       024

💻 코드

/**
 * @file 12000.cpp
 * @author jungbbong
 * @brief 
 * @version 0.1
 * @date 2023-03-19
 * 
 * @copyright Copyright (c) 2023
 * 
 * 최대 5번 움직이기 때문에 그냥 모든 방향의 경우를 계산하자.
 * bfs로 하니 메모리 초과 나와서 dfs로 변경하고, 스택에 넣는 과정 필요없다고 판단.
 * 
 * while문 하나에 ==0 이거 안써서 몇십번을 틀렸다고 나왔다....
 * 코드를 잘 쓰자...
 */

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int result = 0;
int N=0;

int dfs(int curst[20][20],int times){
    times-=1;
    if(times < 0) return 0;
    int nxtst[20][20]={0};
    
    // when move, remove 0 area first, and compare with each other.
    //D
    //remove 0 area
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            nxtst[i][j] = curst[i][j];
        }
    }
    for(int i=0;i<N;i++){
        for(int j=1;j<N;j++){
            if(nxtst[N-j][i]==0){
                int tmp=N-j;
                while(tmp >= 0 && nxtst[tmp][i]==0)
                    tmp-=1;
                if(tmp>-1){
                    nxtst[N-j][i] = nxtst[tmp][i];
                    nxtst[tmp][i]=0;
                }
            }
        }
    }
    // compare up and down
    for(int i=0;i<N;i++){
        for(int j=1;j<N;j++){
            if(nxtst[N-j][i]!=0){
                if(nxtst[N-j][i]==nxtst[N-j-1][i]){
                    nxtst[N-j][i] *= 2;
                    if(nxtst[N-j][i] > result)
                        result = nxtst[N-j][i];
                    for(int k=j+1;k<N;k++){
                        nxtst[N - k][i] = nxtst[N - k -1][i];
                    }
                    nxtst[0][i]=0;
                }
            }
        }
    }
    dfs(nxtst,times);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            nxtst[i][j] = curst[i][j];
        }
    }

    //Up
    //remove 0 
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(nxtst[j][i]==0){
                int tmp = j;
                while(tmp < N && nxtst[tmp][i]==0)
                    tmp+=1;
                if(tmp < N){
                    nxtst[j][i] = nxtst[tmp][i];
                    nxtst[tmp][i]=0;
                }
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(nxtst[j][i]!=0){
                if(nxtst[j][i] == nxtst[j+1][i]){
                    nxtst[j][i] *=2;
                    if(nxtst[j][i] > result)
                        result = nxtst[j][i];
                    for(int k=j+1;k<N-1;k++){
                        nxtst[k][i] = nxtst[k+1][i];
                    }
                    nxtst[N-1][i]=0;
                }
            }
        }
    }
    dfs(nxtst,times);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            nxtst[i][j] = curst[i][j];
        }
    }

    //Right
    for(int i=0;i<N;i++){
        for(int j=1;j<N;j++){
            if(nxtst[i][N-j]==0){
                int tmp=N-j;
                while(tmp >= 0 && nxtst[i][tmp]==0)
                    tmp -=1;
                if(tmp > -1){
                    nxtst[i][N-j] = nxtst[i][tmp];
                    nxtst[i][tmp]=0;
                }
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=1;j<N;j++){
            if(nxtst[i][N-j]!=0){
                if(nxtst[i][N-j]==nxtst[i][N-j-1]){
                    nxtst[i][N-j] *=2;
                    if(nxtst[i][N-j] > result)
                        result = nxtst[i][N-j];
                    for(int k=j+1;k<N;k++){
                        nxtst[i][N-k] = nxtst[i][N-k-1];
                    }
                    nxtst[i][0]=0;
                }
            }
        }
    }
    dfs(nxtst,times);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            nxtst[i][j] = curst[i][j];
        }
    }

    //Left
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(nxtst[i][j]==0){
                int tmp=j;
                while(tmp<N-1 && nxtst[i][tmp]==0)
                    tmp+=1;
                if(tmp < N){
                    nxtst[i][j] = nxtst[i][tmp];
                    nxtst[i][tmp] = 0;
                }
            }        
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(nxtst[i][j]!=0){
                
                if(nxtst[i][j]==nxtst[i][j+1]){
                    nxtst[i][j] *= 2;
                    if(nxtst[i][j] > result)
                        result = nxtst[i][j];
                    for(int k=j+1;k<N-1;k++){
                        nxtst[i][k] = nxtst[i][k+1];
                    }
                    nxtst[i][N-1]=0;
                }
            }
        }
    }
    dfs(nxtst,times);
    return 0;
}

int main(){
    int board[20][20] = {0};
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> board[i][j];
            if(result < board[i][j])
                result = board[i][j];
        }
    }
    dfs(board,5);
    cout << result << "\n";
    
    return 0;
}
profile
아직은 '표류'중인 대학생입니다.

0개의 댓글