[백준] 2048 (Easy)

[hye-on]

🔗 2048 (Easy)

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include using namespace std; //1:17~3:21 ,4:43 int n; long long move(vector>& map, int dir) { //합쳐졌는지 여부 vector> chk(n, vector(n, false)); if (dir == 0) { //아래 for (int j = 0; j < n; j++) { //x축 for (int i = n - 1; i >= 0; i--) { //움직일 필요 없거나 벽쪽이면 스킵 if (map[i][j] == 0 || (i + 1) >= n) continue; int toY = i + 1; while (toY < n) { if (map[toY][j] == 0) { //빈칸이면 map[toY][j] = map[toY - 1][j]; map[toY - 1][j] = 0; } else { if (!chk[toY][j] && !chk[toY - 1][j] && map[toY][j] == map[toY - 1][j]) { //같은 숫자이면 합치기 map[toY][j] *= 2; map[toY - 1][j] = 0; chk[toY][j] = true; } //다른 숫자거나 같은 숫자인데 이미 합친 적이 있으면 아무것도 하지 않음 } toY++; } } } // cout<<"0 ====================="<= 0; j--) { //움직일 필요 없거나 벽쪽이면 스킵 if (map[i][j] == 0 || (j + 1) >= n) continue; int toX = j + 1; while (toX < n) { if (map[i][toX] == 0) { //빈칸이면 map[i][toX] = map[i][toX - 1]; map[i][toX - 1] = 0; } else { if (!chk[i][toX] && !chk[i][toX - 1] && map[i][toX] == map[i][toX - 1]) { //같은 숫자이면 합치기 map[i][toX] *= 2; map[i][toX - 1] = 0; chk[i][toX] = true; } //다른 숫자거나 같은 숫자인데 이미 합친 적이 있으면 아무것도 하지 않음 } toX++; } } } /* cout<<"1=============================="<= 0) { if (map[toY][j] == 0) { //빈칸이면 map[toY][j] = map[toY + 1][j]; map[toY + 1][j] = 0; } else { if (!chk[toY][j] && !chk[toY + 1][j] && map[toY][j] == map[toY + 1][j]) { //같은 숫자이면 합치기 map[toY][j] *= 2; map[toY + 1][j] = 0; chk[toY][j] = true; } //다른 숫자거나 같은 숫자인데 이미 합친 적이 있으면 아무것도 하지 않음 } toY--; } } } // cout<<"2======================="<= 0) { if (map[i][toX] == 0) { //빈칸이면 map[i][toX] = map[i][toX + 1]; map[i][toX + 1] = 0; } else { if (!chk[i][toX] && !chk[i][toX + 1] && map[i][toX] == map[i][toX + 1]) { //같은 숫자이면 합치기 map[i][toX] *= 2; map[i][toX + 1] = 0; chk[i][toX] = true; } //다른 숫자거나 같은 숫자인데 이미 합친 적이 있으면 아무것도 하지 않음 } toX--; } } } // cout<<"3=============================="<> map, int depth) { if (depth == 5) return; //map에서 모든 것을 dir 방향으로 움직이기 for (int i = 0; i < 4; i++) { vector> mapT = map; // cout<<"depth "<> n; vector>board(n, vector(n, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> board[i][j]; } } BruteForce(board, 0); cout << res << endl; return 0; } ```

코멘트

- 출력값 확인하려고 넣었던 코드 한줄 안지워서 계속 틀렸었네요... 게시판 반례 다 넣어보고 왜안돼.. 이러고 있었는데 😢
- 좀 까다로운 구현문제였던것 같아요. 한방향 미루기만 구현하고 회전시키는 방법도 있다는데 그러면 실수를 덜할 것 같아서 좋은것 같아요

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.io.*; import java.util.*; /** * 11:57 START! 12:33 STOP! (35분) * 16:17 RE! 16:41 END! (25분) */ public class Main { /** * 완전탐색 DFS O(4^5*N^2) ~= O(1024N^2) ~= O(N^2) ~= 400 */ static int N; static int answer = 0; public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(bf.readLine()); int[][] board = new int[N][N]; StringTokenizer st; for(int i = 0; i < N; ++i) { st = new StringTokenizer(bf.readLine()); for(int j = 0; j < N; ++j) { board[i][j] = Integer.parseInt(st.nextToken()); } } dfs(0, board); System.out.println(answer); } public static void dfs(int level, int[][] board) { if(level == 5) { int max = 0; for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { max = Math.max(max, board[i][j]); } } answer = Math.max(answer, max); return; } // 상 dfs(level + 1, up(board)); // 하 dfs(level + 1, down(board)); // 좌 dfs(level + 1, left(board)); // 우 dfs(level + 1, right(board)); } public static int[][] up(int[][] board) { int[][] result = new int[N][N]; boolean[][] merged = new boolean[N][N]; for(int i = 0; i < N; ++i) { // i는 col int idx = 0; for(int j = 0; j < N; ++j) { // j는 row if(board[j][i] != 0) { if(idx != 0 && !merged[idx - 1][i] && board[j][i] == result[idx - 1][i]) { result[idx - 1][i] += board[j][i]; merged[idx - 1][i] = true; } else { result[idx++][i] = board[j][i]; } } } } return result; } public static int[][] down(int[][] board) { int[][] result = new int[N][N]; boolean[][] merged = new boolean[N][N]; for(int i = 0; i < N; ++i) { // i는 col int idx = N - 1; for(int j = N - 1; j >= 0; --j) { // j는 row if(board[j][i] != 0) { if(idx != N - 1 && !merged[idx + 1][i] && board[j][i] == result[idx + 1][i]) { result[idx + 1][i] += board[j][i]; merged[idx + 1][i] = true; } else { result[idx--][i] = board[j][i]; } } } } return result; } public static int[][] left(int[][] board) { int[][] result = new int[N][N]; boolean[][] merged = new boolean[N][N]; for(int i = 0; i < N; ++i) { // i는 row int idx = 0; for(int j = 0; j < N; ++j) { // j는 col if(board[i][j] != 0) { if(idx != 0 && !merged[i][idx - 1] && board[i][j] == result[i][idx - 1]) { result[i][idx - 1] += board[i][j]; merged[i][idx - 1] = true; } else { result[i][idx++] = board[i][j]; } } } } return result; } public static int[][] right(int[][] board) { int[][] result = new int[N][N]; boolean[][] merged = new boolean[N][N]; for(int i = 0; i < N; ++i) { // i는 row int idx = N - 1; for(int j = N - 1; j >= 0; --j) { // j는 col if(board[i][j] != 0) { if(idx != N - 1 && !merged[i][idx + 1] && board[i][j] == result[i][idx + 1]) { result[i][idx + 1] += board[i][j]; merged[i][idx + 1] = true; } else { result[i][idx--] = board[i][j]; } } } } return result; } } ```

코멘트

- DFS로 완전탐색을 해도 시간제한이 걸리지 않을 것 같아서, 완탐으로 풀었습니다!
- 상/하/좌/우로 밀어주는 메서드가 따로 있는데, 하나로 합치는 방법도 있을 것 같네요!🧐