12100 2048(Easy) - 삼성 sw 역량 기출

12100

4 * 4 보드에서 블록을 상하좌우로 이동시킨다. 이 때, 같은 값을 같는 블록이 충돌하면 두 블록은 하나로 합쳐지고 값이 더해지게 된다.
한 번 이동에서 이미 합쳐진 블록은 더이상 합쳐지지 않는다.
최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값은?

---

1. 방향대로 합쳐지는 것 구현

   한 번 시간에 두번 합쳐지는 것이 불가능하므로 합친 후에 break를 해줌

   처음에는 +1한 것이 같으면 합쳐지게 구현했는데 0 일 경우가 있으므로 현재 좌표다음 부터 for문을 돌면서

   • 0이 아니고, 같은게 있으면 *2해주고 같은 것이 있던 좌표는 0으로 변경해준후 break;

   • 0이 아니고 다르면 그냥 break;

​

1. 모두 합친 후 방향에 따라서 0 자리를 채워줌

   밀리는 방향 반대로 돌면서 현재 좌표가 0이라면 다음 좌표부터 탐색하며 최초로 0이 아닌 값과 swap해줌 - gravity

   swap 후 break;

   ​

2. 모든 경우의 수 구현

   각 방향으로 미는 경우 전에 맵을 복사한 후 복사한 맵으로 재귀 탐색을 할 수 있도록 구현

   ​

3. 5번 민 후 맵 상태를 검사하여 가장 큰 값 리턴

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main2048 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine().trim());

		int[][] block = new int[N][N];

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

		ans = 0;
		power(block, 0);
		System.out.println(ans);

	}
	static int ans;

	static void power(int[][] block, int cnt) {

		if(cnt == 5) {
			int max = 0;
			for(int i = 0; i < block.length; i++) {
				for(int j = 0; j < block.length; j++) {
					max = Math.max(max, block[i][j]);
				}
			}
			ans = Math.max(max, ans);



			return;
		}
		int[][] copy = new int[block.length][block.length];

		copyMap(block, copy);
		move(copy, 0);
		power(copy, cnt+1);

		copyMap(block, copy);
		move(copy, 1);
		power(copy, cnt+1);

		copyMap(block, copy);
		move(copy, 2);
		power(copy, cnt+1);

		copyMap(block, copy);
		move(copy, 3);
		power(copy, cnt+1);



	}

	static void copyMap(int[][] block, int[][] copy) {
		for(int i = 0; i< block.length; i++) {
			for(int j = 0; j < block.length; j++) {
				copy[i][j] = block[i][j];
			}
		}
	}

	// 상 0 하 1 좌 2 우 3

	static void move(int[][] block, int dir) {
		if(dir == 0) {

			for(int j = 0; j < block.length; j++) {
				for(int i = 0; i < block.length-1; i++) {
					if(block[i][j]!=0) {
						for(int k = i+1; k < block.length; k++) {
							if(block[k][j]!=0) {
								if(block[i][j] == block[k][j]) {
									block[i][j] *= 2;
									block[k][j] = 0;
									break;
 								}else {
 									break;
 								}
							}
						}
					}
				}
				gravityUp(block, j);

			}
		}else if(dir == 1) {
			for(int j = 0; j < block.length; j++) {
				for(int i = block.length-1; i > 0; i--) {
					if(block[i][j]!=0) {
						for(int k = i-1; k >= 0; k--) {
							if(block[k][j]!=0) {
								if(block[i][j] == block[k][j]) {
									block[i][j] *= 2;
									block[k][j] = 0;
									break;
 								}else {
 									break;
 								}
							}
						}
					}
				}
				gravityDown(block, j);
			}
		}else if(dir == 2) {
			for(int i = 0; i < block.length; i++) {
				for(int j = 0; j < block.length-1; j++) {
					if(block[i][j]!=0) {
						for(int k = j+1; k < block.length; k++) {
							if(block[i][k]!=0) {
								if(block[i][j] == block[i][k]) {
									block[i][j] *= 2;
									block[i][k] = 0;
									break;
								}else
									break;
							}
						}
					}
				}
				gravityLeft(block, i);
			}
		}else if(dir == 3) {
			for(int i = 0; i < block.length; i++) {
				for(int j = block.length-1; j > 0; j--) {
					if(block[i][j]!=0) {
						for(int k = j-1; k >= 0; k--) {
							if(block[i][k]!=0) {
								if(block[i][j] == block[i][k]) {
									block[i][j] *= 2;
									block[i][k] = 0;
									break;
								}else
									break;
							}
						}
					}
				}
				gravityRight(block, i);
			}
		}
	}

	static void gravityUp(int[][] block, int x) {
		for(int i = 0; i < block.length-1; i++) {
			if(block[i][x] == 0) {
				for(int j = i+1; j < block.length; j++) {
					if(block[j][x] != 0) {
						int tmp = block[i][x];
						block[i][x] = block[j][x];
						block[j][x] = tmp;
						break;
					}
				}
			}
		}
	}
	static void gravityDown(int[][] block, int x) {
		for(int i = block.length-1; i > 0; i--) {
			if(block[i][x] == 0) {
				for(int j = i-1; j >= 0; j--) {
					if(block[j][x] != 0) {
						int tmp = block[i][x];
						block[i][x] = block[j][x];
						block[j][x] = tmp;
						break;
					}
				}
			}
		}
	}
	static void gravityLeft(int[][] block, int y) {
		for(int i = 0; i < block.length-1; i++) {
			if(block[y][i] == 0) {
				for(int j = i+1; j < block.length; j++) {
					if(block[y][j] != 0) {
						int tmp = block[y][i];
						block[y][i] = block[y][j];
						block[y][j] = tmp;
						break;
					}
				}
			}
		}
	}
	static void gravityRight(int[][] block, int y) {
		for(int i = block.length-1; i > 0; i--) {
			if(block[y][i] == 0) {
				for(int j = i-1; j >= 0; j--) {
					if(block[y][j] != 0) {
						int tmp = block[y][i];
						block[y][i] = block[y][j];
						block[y][j] = tmp;
						break;
					}
				}
			}
		}
	}


}
 ​