끄적끄적 코딩
article thumbnail

브루트포스 문제입니다.

2048게임의 규칙에 따라서 각 위치에 숫자들이 주어졌을때
5번 움직여서 만들 수 있는 가장 큰 수를 구하는 문제입니다.

각 위치에서 상, 하, 좌, 우 4방향으로 5번 움직일 수 있으므로 4^5 경우의 수를 계산해주어야 합니다.
예외처리에서 시간을 많이 사용했는데 주로 사용한 테스트 케이스로는 아래와 같습니다.

3
1 0 1
0 0 0
1 0 1 
ans = 4

각 상하좌우로 한번 씩 움직일 경우 아래와 같이 나오는지 console에 찍어보면서 확인했습니다.
2 0 2  (상)
0 0 0
0 0 0

0 0 0  (하)
0 0 0
2 0 2

2 0 0  (좌)
0 0 0
2 0 0

0 0 2  (우)
0 0 0
0 0 2

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
	static int n;
	static int[][] map;
	static int[] dy = {0, 1, 0, -1};
	static int[] dx = {1, 0, -1, 0};
	static int max = 5;
	static int maxValue = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		map = new int[n][n];
		for(int i=0; i<n; ++i) {
			for(int j=0; j<n; ++j) {
				map[i][j] = sc.nextInt();
			}
		}
		
		for(int i=0; i<4; ++i) {
			DFS(map, i, 0); // 방향, cnt
		}
		
		System.out.println(maxValue);
	}
	public static void DFS(int[][] map, int dir, int cnt) {
		int[][] newMap = new int[n][n];
		for(int i=0; i<n; ++i) {
			for(int j=0; j<n; ++j) {
				newMap[i][j] = map[i][j];
				if(max == cnt) {
					maxValue = Math.max(maxValue,  newMap[i][j]);
				}
			}
		}
		if(max == cnt) {
			return;
		}
		moveMap(newMap, dir);
		
		for(int i=0; i<4; ++i) {
			DFS(newMap, i, cnt+1);
		}
	}
	public static void moveMap(int[][] newMap, int dir) {
		int num;
		int c;
		int arr[] = new int[n];
		switch(dir) {
			case 0: // 오른쪽
				for(int i=0; i<n; ++i) {
					num = 0;
					c = 0;
					for(int j=n-1; j>=0; --j) {
						if(newMap[i][j] == 0) {
							continue;
						}
						if(num == 0) {
							num = newMap[i][j];
							continue;
						}
						if(newMap[i][j] == num) {
							arr[c] = newMap[i][j] * 2;
							num = 0;
							++c;
						} else {
							arr[c] = num;
							num = newMap[i][j];
							++c;
						}
					}
					arr[c] = num;
					for(int j=0; j<n; ++j) {
						newMap[i][n-1-j] = arr[j];
						arr[j] = 0;
					}
				}
				break;
			case 1: // 아래
				for(int i=0; i<n; ++i) {
					num = 0;
					c = 0;
					for(int j=n-1; j>=0; --j) {
						if(newMap[j][i] == 0) {
							continue;
						}
						if(num == 0) {
							num = newMap[j][i];
							continue;
						}
						if(newMap[j][i] == num) {
							arr[c] = newMap[j][i] * 2;
							num = 0;
							++c;
						} else {
							arr[c] = num;
							num = newMap[j][i];
							++c;
						}
					}
					arr[c] = num;
					for(int j=0; j<n; ++j) {
						newMap[n-1-j][i] = arr[j];
						arr[j] = 0;
					}
				}
				break;
			case 2: // 왼쪽
				for(int i=0; i<n; ++i) {
					num = 0;
					c = 0;
					for(int j=0; j<n; ++j) {
						if(newMap[i][j] == 0) {
							continue;
						}
						if(num == 0) {
							num = newMap[i][j];
							continue;
						}
						if(newMap[i][j] == num) {
							arr[c] = newMap[i][j] * 2;
							num = 0;
							++c;
						} else {
							arr[c] = num;
							num = newMap[i][j];
							++c;
						}
					}
					arr[c] = num;					
					for(int j=0; j<n; ++j) {
						newMap[i][j] = arr[j];
						arr[j] = 0;
					}
				}
			break;
			case 3: // 위
				for(int i=0; i<n; ++i) {
					num = 0;
					c = 0;
					for(int j=0; j<n; ++j) {
						if(newMap[j][i] == 0) {
							continue;
						}
						if(num == 0) {
							num = newMap[j][i];
							continue;
						}
						if(newMap[j][i] == num) {
							arr[c] = newMap[j][i] * 2;
							num = 0;
							++c;
						} else {
							arr[c] = num;
							num = newMap[j][i];
							++c;
						}
					}
					arr[c] = num;
					for(int j=0; j<n; ++j) {
						newMap[j][i] = arr[j];
						arr[j] = 0;
					}
				}
				break;
		}
	}
}

'알고리즘' 카테고리의 다른 글

[Java] 백준 14499번 주사위 굴리기  (0) 2023.02.01
[Java] 백준 14890번 경사로  (0) 2023.01.30
[Java] 백준 3190번 뱀  (0) 2023.01.29
[Java] 백준 14502번 연구소  (0) 2023.01.26
[Java] 백준 14501번 퇴사  (0) 2023.01.25

검색 태그