문제

백준 12100 2048 (Easy) 문제 보러가기



문제점 해결

한 번 합쳐진 블록은 합쳐질 수 없다는 부분을 잘못 이해해서 시간이 걸린 문제였다. 해당 문제는 BFS를 사용해 풀 수 있는 문제이고 한 방향으로 밀때 0인 빈공간을 메워준 후 숫자를 합치고 다시 0으로 빈 공간을 메워주는 과정을 반복했다.

0인 빈공간을 메울때 너무 꼬아서 생각할 필요없이 크기가 같은 map 배열을 하나 만들어서 예를 들어 왼쪽 방향으로 민다면 열의 0번째 부터 차곡차곡 값을 쌓아준다고 생각하면 된다.

for (int i = 0; i < N; i++) {
    int newj = 0;
    for (int j = 0; j < N; j++) {
        if (originMap[i][j] != 0)
            moveMap[i][newj++] = originMap[i][j];
    }
}



풀이

import java.io.*;

public class Main {
	static int N, answer;
	static int[][] dir = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		int[][] map = new int[N][N];

		for (int i = 0; i < N; i++) {
			String[] s = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(s[j]);
			}
		}

		if (N == 1) {
			System.out.println(map[0][0]);
			return;
		}

		answer = 0;
		bfs(map, 0);
		System.out.println(answer);
	}

	public static void bfs(int[][] map, int count) {
		if (count == 5) {
			answer = Math.max(checkMaxValue(map), answer);
			return;
		}

		for (int d = 0; d < 4; d++) {
			int[][] moveMap = move(map, d); // 0인 부분 일단 밀어서 메워주기
			moveMap = merge(moveMap, d);
			moveMap = move(moveMap, d);
			bfs(moveMap, count + 1);
		}
	}

	private static int[][] merge(int[][] map, int d) {
		int ni = 0, nj = 0;
		
		switch (d) {
		case 0:
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j > 0; j--) {
					ni = i + dir[d][0];
					nj = j + dir[d][1];
					
					if(map[i][j] == map[ni][nj]) {
						map[i][j] += map[ni][nj];
						map[ni][nj] = 0;
					}
				}
			}
			break;
		case 1:
			for (int j = 0; j < N; j++) {
				for (int i = N - 1; i > 0; i--) {
					ni = i + dir[d][0];
					nj = j + dir[d][1];
					
					if(map[i][j] == map[ni][nj]) {
						map[i][j] += map[ni][nj];
						map[ni][nj] = 0;
					}
				}
			}
			break;
		case 2:
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N - 1; j++) {
					ni = i + dir[d][0];
					nj = j + dir[d][1];
					
					if(map[i][j] == map[ni][nj]) {
						map[i][j] += map[ni][nj];
						map[ni][nj] = 0;
					}
				}
			}
			break;
		default:
			for (int j = 0; j < N; j++) {
				for (int i = 0; i < N - 1; i++) {
					ni = i + dir[d][0];
					nj = j + dir[d][1];
					
					if(map[i][j] == map[ni][nj]) {
						map[i][j] += map[ni][nj];
						map[ni][nj] = 0;
					}
				}
			}
			break;
		}
		
		return map;
	}

	private static int[][] move(int[][] originMap, int d) {
		int[][] moveMap = new int[N][N];
		switch (d) {
		case 0: // 오른쪽
			for (int i = 0; i < N; i++) {
				int newj = N - 1;
				for (int j = N - 1; j >= 0; j--) {
					if (originMap[i][j] != 0) // originMap의 0이 아닌 값을 moveMap에 차곡차곡 쌓는다고 생각
						moveMap[i][newj--] = originMap[i][j];
				}
			}
			break;
		case 1: // 아래
			for (int j = 0; j < N; j++) {
				int newi = N - 1;
				for (int i = N - 1; i >= 0; i--) {
					if (originMap[i][j] != 0)
						moveMap[newi--][j] = originMap[i][j];
				}
			}
			break;
		case 2: // 왼쪽
			for (int i = 0; i < N; i++) {
				int newj = 0;
				for (int j = 0; j < N; j++) {
					if (originMap[i][j] != 0)
						moveMap[i][newj++] = originMap[i][j];
				}
			}
			break;
		default: // 위
			for (int j = 0; j < N; j++) {
				int newi = 0;
				for (int i = 0; i < N; i++) {
					if (originMap[i][j] != 0)
						moveMap[newi++][j] = originMap[i][j];
				}
			}
			break;
		}

		return moveMap;
	}

	private static int checkMaxValue(int[][] map) {
		int max = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				max = Math.max(max, map[i][j]);
			}
		}

		return max;
	}
}