백준_2048 (Easy)_12100

// 알고리즘

1. 시뮬? + 완탐

 

2. 최대 5번 이동이 가능하기 때문에 0~4까지 갈 수 있는 모든 이동방향을 구함

 -> 재귀로 해결

 

3. 각 이동방향마다 시뮬레이션

 -> 위 방향일 때 하나만 구현하면 아래 왼쪽 오른쪽은 비슷한 코드가 됨.

 -> 계산된 값은 또 더해지면 안됨 ex) 2 2 2 2 -> 4 4 0 0 (왼쪽)

 -> 위 경우를 해결하기 위해 방문배열 사용(v[N][N])

import java.io.*;
import java.util.*;

public class Easy2048_12100 {
	
	  static int N, map[][], dir[], ans;
	   static int[] dr = { 1, -1, 0, 0 }; // 하 상 우 좌
	   static int[] dc = { 0, 0, 1, -1 };

	   public static void main(String[] args) throws Exception {
	      // 2048 (Easy)_ 12100
	      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	      N = Integer.parseInt(br.readLine());

	      map = new int[N][N];

	      for (int i = 0; i < N; i++) {
	         StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	         for (int j = 0; j < N; j++) {
	            map[i][j] = Integer.parseInt(st.nextToken());
	         }
	      }

	      dir = new int[5];

	      // 알고리즘
	      cal(0);
	      System.out.println(ans);

	   }

	   private static void cal(int idx) {
	      if (idx == 5) {
	         // 계산
	         int[][] nMap = new int[N][N];
	         copy(nMap);
	         for (Integer i : dir) {
	            go(i, nMap);
	         }

	         maxCal(nMap);

	         return;
	      }

	      for (int j = 0; j < 4; j++) {
	         dir[idx] = j;
	         cal(idx + 1);
	      }

	   }

	   private static void maxCal(int[][] nMap) {

	      for (int i = 0; i < nMap.length; i++) {
	         for (int j = 0; j < nMap[i].length; j++) {
	            if (ans < nMap[i][j])
	               ans = nMap[i][j];
	         }
	      }

	   }

	   private static void go(Integer i, int[][] nMap) {

	      boolean[][] v = new boolean[N][N];
	      switch (i) {
	      case 0:
	         // 하
	         for (int r = N - 2; r >= 0; r--) {
	            int idx = r;

	            while (true) {
	               if (idx == N - 1)
	                  break;
	               for (int c = 0; c < nMap.length; c++) {
	                  if (nMap[idx][c] == 0)
	                     continue;
	                  if (nMap[idx][c] != nMap[idx + 1][c] && nMap[idx + 1][c] != 0)
	                     continue;
	                  if (v[idx][c])
	                     continue;
	                  if (nMap[idx + 1][c] != 0) {
	                     v[idx][c] = true;
	                     v[idx + 1][c] = true;
	                  }
	                  nMap[idx + 1][c] += nMap[idx][c];
	                  nMap[idx][c] = 0;
	               }
	               idx += 1;
	            }

	         }
	         break;
	      case 1:
	         // 상
	         for (int r = 1; r < N; r++) {
	            int idx = r;
	            while (true) {
	               if (idx == 0)
	                  break;
	               for (int c = 0; c < nMap.length; c++) {
	                  if (nMap[idx][c] == 0)
	                     continue;
	                  if (nMap[idx][c] != nMap[idx - 1][c] && nMap[idx - 1][c] != 0)
	                     continue;
	                  if (v[idx][c])
	                     continue;
	                  if (nMap[idx - 1][c] != 0) {
	                     v[idx][c] = true;
	                     v[idx - 1][c] = true;
	                  }
	                  nMap[idx - 1][c] += nMap[idx][c];
	                  nMap[idx][c] = 0;
	               }
	               idx -= 1;
	            }

	         }
	         break;
	      case 2:
	         // 우
	         for (int r = N - 2; r >= 0; r--) {
	            int idx = r;

	            while (true) {
	               if (idx == N - 1)
	                  break;
	               for (int c = 0; c < nMap.length; c++) {
	                  if (nMap[c][idx] == 0)
	                     continue;
	                  if (nMap[c][idx] != nMap[c][idx + 1] && nMap[c][idx + 1] != 0)
	                     continue;
	                  if (v[c][idx])
	                     continue;
	                  if (nMap[c][idx + 1] != 0) {
	                     v[c][idx] = true;
	                     v[c][idx + 1] = true;
	                  }
	                  nMap[c][idx + 1] += nMap[c][idx];
	                  nMap[c][idx] = 0;
	               }
	               idx += 1;
	            }

	         }
	         break;
	      case 3:
	         // 좌
	         for (int r = 1; r < N; r++) {
	            int idx = r;
	            while (true) {
	               if (idx == 0)
	                  break;
	               for (int c = 0; c < nMap.length; c++) {
	                  if (nMap[c][idx] == 0)
	                     continue;
	                  if (nMap[c][idx] != nMap[c][idx - 1] && nMap[c][idx - 1] != 0)
	                     continue;
	                  if (v[c][idx])
	                     continue;
	                  if (nMap[c][idx - 1] != 0) {
	                     v[c][idx] = true;
	                     v[c][idx - 1] = true;
	                  }
	                  nMap[c][idx - 1] += nMap[c][idx];
	                  nMap[c][idx] = 0;
	               }
	               idx -= 1;
	            }

	         }
	         break;
	      }

	   }

	   private static void copy(int[][] nMap) {
	      for (int i = 0; i < N; i++) {
	         for (int j = 0; j < N; j++) {
	            nMap[i][j] = map[i][j];
	         }
	      }

	   }


}

※ 시뮬을 오랜만에 풀어봐서 시간이 상당히 오래걸림.. 이전에 비슷한 문제를 풀어보긴했는데 그 때와 전혀 다른 코드로 구현함.