본문 바로가기
알고리즘/백준

[백준] 12100번 2048(Easy)

여우와펭귄 2019. 10. 3. 13:50
반응형

12100번 2048(Easy)

  1. 이해하기
    • 한 번의 이동은 보드 위에 있는 블록을 같은 방향으로 이동시킨다.
    • 이동했을 때 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐진다.
    • 같은 이동에서 합쳐진 블록은 다른 블록과 다시 합쳐질 수 없다.
    • 최대 5번의 이동을 통해 만들어 질 수 있는 블록의 최대값을 구한다.
    • 블록을 최대 횟수까지 이동시키며 상태를 보는 완전탐색 문제.

  1. 구현하기

    • 한번의 방향으로 이동시키면서 같은 값의 블록이 충돌하면 두 블록을 하나로 합치고 이미 합쳐진 블록은 다른 블록과 합쳐지지 못하게 check배열을 이용한다.

      vector<vector<int>> move(vector<vector<int>> map, int dir) {
    vector<vector<int>> ret(N,vector<int>(N));
    memset(check,false,sizeof(check));
    if(dir == 0) {
        for(int i = 1; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(map[i][j] == 0) continue;
                int x = i, y = j;
                while(x-1 >= 0) {
                    if(map[x-1][y] == 0) {
                        map[x-1][y] = map[x][y]; map[x][y] = 0;
                    } else {
                        if(map[x-1][y] == map[x][y] and check[x-1][y] == false) {
                            map[x-1][y] += map[x][y]; check[x-1][y] = true; map[x][y] = 0;
                            break;
                        } else break;
                    }
                    x -= 1;
                }
            }
        }
    } else if(dir == 1) {
        for(int i = N-2; i >= 0; i--) {
            for(int j = 0; j < N; j++) {
                if(map[i][j] == 0) continue;
                int x = i, y = j;
                while(x+1 < N) {
                    if(map[x+1][y] == 0) {
                        map[x+1][y] = map[x][y]; map[x][y] = 0;
                    } else {
                        if(map[x+1][y] == map[x][y] and check[x+1][y] == false) {
                            map[x+1][y] += map[x][y]; check[x+1][y] = true; map[x][y] = 0;
                            break;
                        } else break;
                    }
                    x+=1;
                }
            }
        }
    } else if(dir == 2) {
        for(int i = 0; i < N; i++) {
            for(int j = 1; j < N; j++) {
                if(map[i][j] == 0) continue;
                int x = i, y = j;
                while(y-1 >= 0) {
                    if(map[x][y-1] == 0) {
                        map[x][y-1] = map[x][y]; map[x][y] = 0;
                    } else {
                        if(map[x][y-1] == map[x][y] and !check[x][y-1]) {
                            map[x][y-1]*=2; check[x][y-1] = true; map[x][y] = 0;
                            break;
                        } else break;
                    }
                    y-=1;
                }
            }
        }
    } else if(dir == 3) {
        for(int i = 0; i < N; i++) {
            for(int j = N-2; j >= 0; j--) {
                if(map[i][j] == 0) continue;
                int x = i, y = j;
                while(y+1 < N) {
                    if(map[x][y+1] == 0) {
                        map[x][y+1] = map[x][y]; map[x][y] = 0;
                    } else {
                        if(map[x][y+1] == map[x][y] and !check[x][y+1]) {
                            map[x][y+1]*=2; check[x][y+1] = true; map[x][y] = 0;
                            break;
                        } else break;
                    }
                    y+=1;
                }
            }
        }
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            ret[i][j] = map[i][j];
        }
    }
    return ret;
}

    • 최대 5번의 이동을 통해서 나올 수 있는 블록의 최대값을 구한다.

      int solve(vector<vector<int>> map, int cnt) {
    if(cnt == 5) {
        int max = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(max < map[i][j]) max = map[i][j];
            }
        }
        return max;
    }

    int ret = 0;
    vector<vector<int>> t_map;
    for(int i = 0; i < 4; i++) {
        t_map = move(map,i);
        ret = max(ret,solve(t_map,cnt+1));
    }
    return ret;
}

  1. 전체 코드

    #include <iostream>
#include <cstring>
#include <vector>
using namespace std;
bool check[20][20];
int N;

vector<vector<int>> move(vector<vector<int>> map, int dir) {
    vector<vector<int>> ret(N,vector<int>(N));
    memset(check,false,sizeof(check));
    if(dir == 0) {
        for(int i = 1; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(map[i][j] == 0) continue;
                int x = i, y = j;
                while(x-1 >= 0) {
                    if(map[x-1][y] == 0) {
                        map[x-1][y] = map[x][y]; map[x][y] = 0;
                    } else {
                        if(map[x-1][y] == map[x][y] and check[x-1][y] == false) {
                            map[x-1][y] += map[x][y]; check[x-1][y] = true; map[x][y] = 0;
                            break;
                        } else break;
                    }
                    x -= 1;
                }
            }
        }
    } else if(dir == 1) {
        for(int i = N-2; i >= 0; i--) {
            for(int j = 0; j < N; j++) {
                if(map[i][j] == 0) continue;
                int x = i, y = j;
                while(x+1 < N) {
                    if(map[x+1][y] == 0) {
                        map[x+1][y] = map[x][y]; map[x][y] = 0;
                    } else {
                        if(map[x+1][y] == map[x][y] and check[x+1][y] == false) {
                            map[x+1][y] += map[x][y]; check[x+1][y] = true; map[x][y] = 0;
                            break;
                        } else break;
                    }
                    x+=1;
                }
            }
        }
    } else if(dir == 2) {
        for(int i = 0; i < N; i++) {
            for(int j = 1; j < N; j++) {
                if(map[i][j] == 0) continue;
                int x = i, y = j;
                while(y-1 >= 0) {
                    if(map[x][y-1] == 0) {
                        map[x][y-1] = map[x][y]; map[x][y] = 0;
                    } else {
                        if(map[x][y-1] == map[x][y] and !check[x][y-1]) {
                            map[x][y-1]*=2; check[x][y-1] = true; map[x][y] = 0;
                            break;
                        } else break;
                    }
                    y-=1;
                }
            }
        }
    } else if(dir == 3) {
        for(int i = 0; i < N; i++) {
            for(int j = N-2; j >= 0; j--) {
                if(map[i][j] == 0) continue;
                int x = i, y = j;
                while(y+1 < N) {
                    if(map[x][y+1] == 0) {
                        map[x][y+1] = map[x][y]; map[x][y] = 0;
                    } else {
                        if(map[x][y+1] == map[x][y] and !check[x][y+1]) {
                            map[x][y+1]*=2; check[x][y+1] = true; map[x][y] = 0;
                            break;
                        } else break;
                    }
                    y+=1;
                }
            }
        }
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            ret[i][j] = map[i][j];
        }
    }
    return ret;
}

int solve(vector<vector<int>> map, int cnt) {
    if(cnt == 5) {
        int max = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(max < map[i][j]) max = map[i][j];
            }
        }
        return max;
    }

    int ret = 0;
    vector<vector<int>> t_map;
    for(int i = 0; i < 4; i++) {
        t_map = move(map,i);
        ret = max(ret,solve(t_map,cnt+1));
    }
    return ret;
}

int main() {
    cin >> N;
    vector<vector<int>> map(N, vector<int>(N));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }

    cout << solve(map,0) << '\n';
    return 0;
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 13458번 시험 감독  (0) 2019.10.03
[백준] 3190번 뱀  (0) 2019.10.03
[백준] 13460번 구슬 탈출2  (0) 2019.10.03
7576. 토마토  (0) 2018.11.15
1259. 팰린드롬수  (0) 2018.11.13

'알고리즘/백준' Related Articles

티스토리툴바