[백준 / BOJ] 12100번 : 2048 (Easy) (JAVA)

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

한 쪽으로 몰기

위, 아래, 왼쪽, 오른쪽으로 이동시키는 기본 개념은 똑같기 때문에 위로 움직이는 것을 가장 먼저 만들고 나머지는 i와 j의 위치, 시작하는 위치를 조금 바꿔주기만 했다.

private static void move_up(int[][] map) {

    int N = map.length;

    for (int j = 0; j < N; j++) {
        int o = 0;
        for (int i = 1; i < N; i++) {
            if(map[i][j] == 0) continue;
            if(map[o][j] == 0) {
                map[o][j] = map[i][j];
                map[i][j] = 0;
            } else if(map[o][j] == map[i][j]) {
                map[o][j] += map[o][j];
                map[i][j] = 0;
                o++;
            } else {
                o++;
                map[o][j] = map[i][j];
                if(o != i) map[i][j] = 0;
            }
        }
    }
}

위로 움직일 때에는 열은 고정이고 박스의 행을 바꿔야 하기 때문에 j가 바깥, i가 안쪽에 위치한다.

 

변수 o는 박스를 옮길 행이다. 이에 따라 박스를 옮기는 조건은 다음과 같다.

1. o행이 비어있다면(0이라면) i번째 숫자를 o행으로 옮긴다. o는 변하지 않는다.
2. o행에 숫자가 있고 i번째 숫자와 같다면 o행의 값을 두 배로 올린다. i번째 숫자는 지우고, o는 다음 행을 가리키도록 한다.
3. o행에 숫자가 있고 i번째 숫자와 다르다면 o가 다음 행을 가리키도록 한 위 i번째 숫자를 옮겨준다.

i번째 숫자를 옮긴 후에는 꼭 원래 자리를 0으로 바꿔주도록 했다. 단, 3번의 경우 바로 o와 i가 같을 수도 있기 때문에 값이 다른 경우에만 0으로 바꾸도록 조건을 붙였다.

 

최댓값 찾기

총 5번만 움직이면 되고, 한 턴에 움직일 수 있는 방법은 4개이기 때문에 4^5 = 1024 개의 경우의 수가 있다. 또한 함수 내에서 또 다시 함수를 호출하더라도 스택이 최대 5개밖에 쌓이지 않기 때문에 stackoverflow가 날 수도 없어서 그냥 중첩 함수로 진행했다.

 

cnt로 몇 번 움직였는지 확인하고 cnt == 5가 되면 map을 전부 돌면서 가장 큰 숫자를 찾도록 했다.

 

전체 코드

// 시간 : 136ms
// 메모리 : 17024KB
public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] map = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		max = 0;
		move_2048(0, map);
		
		System.out.println(max);
	}

	static int max;
	private static void move_2048(int cnt, int[][] map) {
		
		int N = map.length;
		if(cnt == 5) {
			int m = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(m < map[i][j]) m = map[i][j];
				}
			}
			max = Math.max(max, m);
			return;
		}
		
		int[][] tmp = new int[N][N];
		reset_map(tmp, map);
		
		move_up(tmp);
		move_2048(cnt + 1, tmp);
		reset_map(tmp, map);
		
		move_down(tmp);
		move_2048(cnt + 1, tmp);
		reset_map(tmp, map);
		
		move_left(tmp);
		move_2048(cnt + 1, tmp);
		reset_map(tmp, map);
		
		move_right(tmp);
		move_2048(cnt + 1, tmp);
		reset_map(tmp, map);
	}
	
	
	private static void move_right(int[][] map) {

		int N = map.length;
		
		for (int i = 0; i < N; i++) {
			int o = N - 1;
			for (int j = N - 2; j >= 0; j--) {
				if(map[i][j] == 0) continue;
				if(map[i][o] == 0) {
					map[i][o] = map[i][j];
					map[i][j] = 0;
				} else if(map[i][o] == map[i][j]) {
					map[i][o] += map[i][o];
					map[i][j] = 0;
					o--;
				} else {
					o--;
					map[i][o] = map[i][j];
					if(o != j) map[i][j] = 0;
				}
			}
		}
	}


	private static void move_left(int[][] map) {

		int N = map.length;
		
		for (int i = 0; i < N; i++) {
			int o = 0;
			for (int j = 1; j < N; j++) {
				if(map[i][j] == 0) continue;
				if(map[i][o] == 0) {
					map[i][o] = map[i][j];
					map[i][j] = 0;
				} else if(map[i][o] == map[i][j]) {
					map[i][o] += map[i][o];
					map[i][j] = 0;
					o++;
				} else {
					o++;
					map[i][o] = map[i][j];
					if(o != j) map[i][j] = 0;
				}
			}
		}
	}


	private static void move_down(int[][] map) {
		int N = map.length;
		
		for (int j = 0; j < N; j++) {
			int o = N - 1;
			for (int i = N - 2; i >= 0; i--) {
				if(map[i][j] == 0) continue;
				if(map[o][j] == 0) {
					map[o][j] = map[i][j];
					map[i][j] = 0;
				} else if(map[o][j] == map[i][j]) {
					map[o][j] += map[o][j];
					map[i][j] = 0;
					o--;
				} else {
					o--;
					map[o][j] = map[i][j];
					if(o != i) map[i][j] = 0;
				}
			}
		}		
	}


	private static void move_up(int[][] map) {
		
		int N = map.length;
		
		for (int j = 0; j < N; j++) {
			int o = 0;
			for (int i = 1; i < N; i++) {
				if(map[i][j] == 0) continue;
				if(map[o][j] == 0) {
					map[o][j] = map[i][j];
					map[i][j] = 0;
				} else if(map[o][j] == map[i][j]) {
					map[o][j] += map[o][j];
					map[i][j] = 0;
					o++;
				} else {
					o++;
					map[o][j] = map[i][j];
					if(o != i) map[i][j] = 0;
				}
			}
		}
	}


	private static void reset_map(int[][] tmp, int[][] map) {

		int N = map.length;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				tmp[i][j] = map[i][j];
			}
		}
	}

}