알고리즘 풀이/백준(Boj)
백준(BOJ) 12100번 2048 (Easy)
100win10
2019. 12. 15. 15:55
문제 : https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
풀이 :
solve 함수는 각 함수마다 위쪽 아래쪽 왼쪽 오른쪽으로 배열 a를 몰아준 후에 cnt가 5가 될 때까지 재귀 함수를 돌린다.
5번 다 몰았다면 이때 가장 큰값은 2중 for문을 통해 best에 저장한다.
코드 ( C++ )
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| using namespace std; | |
| int n; | |
| int best; | |
| vector<vector<int>> up(vector<vector<int>> a) | |
| { | |
| vector<vector<bool>> onlyOne(n, vector<bool>(n)); | |
| for(int i=0; i<n; ++i) | |
| for (int j = 0; j < n; ++j) | |
| { | |
| int y = i; | |
| // 이동 | |
| while (y > 0 && a[y-1][j] == 0) { | |
| a[y-1][j] = a[y][j]; | |
| a[y][j] = 0; | |
| y--; | |
| } | |
| // 합치기 | |
| if (y > 0 && a[y - 1][j] == a[y][j] && !onlyOne[y-1][j]) { | |
| onlyOne[y - 1][j] = true; | |
| a[y - 1][j] *= 2; | |
| a[y][j] = 0; | |
| } | |
| } | |
| return a; | |
| } | |
| vector<vector<int>> down(vector<vector<int>> a) | |
| { | |
| vector<vector<bool>> onlyOne(n, vector<bool>(n)); | |
| for (int i = n-1; i >= 0; --i) | |
| for (int j = 0; j < n; ++j) | |
| { | |
| int y = i; | |
| // 이동 | |
| while (y < n-1 && a[y + 1][j] == 0) { | |
| a[y + 1][j] = a[y][j]; | |
| a[y][j] = 0; | |
| y++; | |
| } | |
| // 합치기 | |
| if (y < n-1 && a[y + 1][j] == a[y][j] && !onlyOne[y + 1][j]) { | |
| onlyOne[y + 1][j] = true; | |
| a[y + 1][j] *= 2; | |
| a[y][j] = 0; | |
| } | |
| } | |
| return a; | |
| } | |
| vector<vector<int>> left(vector<vector<int>> a) | |
| { | |
| vector<vector<bool>> onlyOne(n, vector<bool>(n)); | |
| for (int i = 0; i < n; ++i) | |
| for (int j = 0; j < n; ++j) | |
| { | |
| int x = j; | |
| // 이동 | |
| while (x > 0 && a[i][x - 1] == 0) { | |
| a[i][x - 1] = a[i][x]; | |
| a[i][x] = 0; | |
| x--; | |
| } | |
| // 합치기 | |
| if (x > 0 && a[i][x - 1] == a[i][x] && !onlyOne[i][x - 1]) { | |
| onlyOne[i][x - 1] = true; | |
| a[i][x - 1] *= 2; | |
| a[i][x] = 0; | |
| } | |
| } | |
| return a; | |
| } | |
| vector<vector<int>> right(vector<vector<int>> a) | |
| { | |
| vector<vector<bool>> onlyOne(n, vector<bool>(n)); | |
| for (int i = 0; i < n; ++i) | |
| for (int j = n - 1; j >= 0; --j) | |
| { | |
| int x = j; | |
| // 이동 | |
| while (x < n-1 && a[i][x+1] == 0) { | |
| a[i][x+1] = a[i][x]; | |
| a[i][x] = 0; | |
| x++; | |
| } | |
| // 합치기 | |
| if (x < n-1 && a[i][x+1] == a[i][x] && !onlyOne[i][x+1]) { | |
| onlyOne[i][x+1] = true; | |
| a[i][x+1] *= 2; | |
| a[i][x] = 0; | |
| } | |
| } | |
| return a; | |
| } | |
| void solve(vector<vector<int>> a, int cnt) | |
| { | |
| if (cnt == 5) | |
| { | |
| for (int i = 0; i < n; ++i) | |
| for (int j = 0; j < n; ++j) | |
| if (best < a[i][j]) | |
| best = a[i][j]; | |
| return; | |
| } | |
| solve(up(a), cnt + 1); | |
| solve(down(a), cnt + 1); | |
| solve(left(a), cnt + 1); | |
| solve(right(a), cnt + 1); | |
| } | |
| int main() | |
| { | |
| vector<vector<int>> a; | |
| cin >> n; | |
| a = vector<vector<int>>(n, vector<int>(n)); | |
| for (int i = 0; i < n; ++i) | |
| for (int j = 0; j < n; ++j) | |
| cin >> a[i][j]; | |
| solve(a, 0); | |
| cout << best << "\n"; | |
| return 0; | |
| } |
