BOJ - 2048(Easy)

12100 2048(Easy) : https://www.acmicpc.net/problem/12100

---

Problem

---

Solve

보드의 블럭을 상,하,좌,우 이동시키면서 같은 값을 가지는 블럭을 만났을때 블럭을 합쳐 보드에서 최대의 값을 반환하는 문제입니다.

가장 많이 고민했던 부분은 블럭을 어떻게 상,하,좌,우를 공통으로 만들어 구현할수 있을것인가와 충돌한 블럭을 어떻게 합칠까 였습니다.

먼저 충돌한 블럭을 이전 좌표에 있는 블럭을 하나하나 비교하려니 너무 복잡했습니다. 그러다 문득 좌표에있는 블럭을 비교하지 말고 어딘가에 들어있는 블럭을 비교해보자 생각했습니다.
순차적으로 쌓이는 블럭을 저장하고 마지막 블럭을 꺼내고, 앞에서부터 순차적으로 블럭을 꺼내 배열에 저장하는 기능이 필요했기 때문에 Deque를 사용했습니다.

예를 들어 위쪽으로 블럭을 이동시킬때, Deque가 비어있다면 앞에는 블럭이 존재하지 않기 때문에 Deque에 해당 블럭을 넣어줍니다.
그리고 Deque가 비어있지 않고 현재 블럭 값과 동일하다면 Deque에서 값을 빼어 현재 블럭의 2배로 넣어줍니다.
이때 주의할 점은 블럭이 0이면 안되고 이전에 충돌로 인해 한번 합쳐진 블럭이어서는 안됩니다.

그리고 한쪽 블럭을 모두 합쳐줬다면 블럭을 순차적으로 배열에 저장해줍니다.

static int[][] moveOfDir(int[][] map){
		//이동한 블럭을 담을 새로운 배열
		int[][] newMap = new int[N][N];

		//배열을 왼쪽에서 오른쪽으로 이동하며 블럭을 위쪽으로 이동시켜줍니다.
		for(int x=0;x<N;x++){
        
			Deque<Block> dq = new ArrayDeque();
            
            //해당 x좌표에서 위쪽으로 이동하기 때문에 위쪽에서 아래쪽으로 이동하며 조건에 맞게 Deque에 블럭을 저장해줍니다.
			for(int y=0;y<N;y++){
            
            	//덱이 비어있지않고 현재 블럭이 0이 아니고 
                //덱의 마지막 값과 현재 블럭 값이 동일하고 덱의 마지막 블럭이 이전에 충돌한 기록이 없는 경우
				if(!dq.isEmpty() && map[y][x] != 0 && dq.peekLast().num == map[y][x] && !dq.peekLast().crash){
                
                	//덱의 마지막 블럭을 꺼내고 현재 블럭의 두배의 값을 덱에 넣어줍니다.
                    //두 블럭이 충돌했으니 true
					dq.pollLast();
					dq.offerLast(new Block(map[y][x]*2, true));  
				}
                //블럭이 0이면 빈공간입니다.
                else if(map[y][x] != 0){
                
                	//두 블럭이 충돌하지 않았으니 false
					dq.offerLast(new Block(map[y][x], false));
				}
			}

			//위쪽에서 부터 순차적으로 블럭 쌓아주기
			int y=0;
			while(!dq.isEmpty()){
				newMap[y++][x] = dq.pollFirst().num;
			}
		}

		return newMap;
	}

만약 코드를 보셨다면, 의문점이 있을겁니다.
문제에서는 블럭을 상,하,좌,우로 이동하는것을 요구하는데 코드에서는 위쪽으로만 블럭을 이동시키는지 말입니다.

이유는 구현과정에서 고민했던 부분인 상,하,좌,우를 이동하는 코드를 공통으로 쓰게 하는 것이 이유입니다.

블럭을 직관적으로 상,하,좌,우로 이동시켜줄수 있지만, 만약 보드를 회전시켜준다면 블럭을 한쪽 방향으로만 이동시켜도 모든 방향으로 이동하는것이 됩니다.

	//왼쪽 방향으로 90도 회전
	static int[][] turn(int[][] map){
		int[][] newMap = new int[N][N];

		for(int y=0;y<N;y++){
			for(int x=0;x<N;x++){
				newMap[y][x] = map[x][N-1-y];
			}
		}

		return newMap;
	}

다행히 이전에 백준 문제에서 2차원배열 회전문제를 풀었던 경험이 도움이 되었습니다.

그렇다면 재귀를 이용해서 주어진 보드를 4번 회전시키는 동안 각각 위로 이동시키고 재귀호출을 depth==5가 될때까지 반복한다면, 모든 방향으로의 경우를 구할수있게됩니다.

	static void move(int[][] map, int depth) {
		if (depth == 5) {
			int maxValue = findMax(map);
			answer = Math.max(maxValue, answer);
			return;
		}

        //왼쪽으로 90도씩 4번 회전
		for(int i=0;i<4;i++){
        	//회전
			map = turn(map);
            
            //위로 이동
			int[][] moveMap = moveOfDir(map);
            
            //재귀 호출
			move(moveMap, depth+1);
		}
	}

---

Code

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	static int answer = 0;
	static int N;

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

		N = Integer.parseInt(br.readLine());
		int[][] 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());
			}
		}

		answer = 0;
		move(map, 0);

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static void move(int[][] map, int depth) {
		if (depth == 5) {
			int maxValue = findMax(map);
			answer = Math.max(maxValue, answer);
			return;
		}
        
        for(int i=0;i<4;i++){
            map = turn(map);
            int[][] moveMap = moveOfDir(map);
            move(moveMap, depth+1);
        }

	}
    
    static int[][] turn(int[][] map){
        int[][] newMap = new int[N][N];
        
        for(int y=0;y<N;y++){
            for(int x=0;x<N;x++){
                newMap[y][x] = map[x][N-1-y];
            }
        }
        
        return newMap;
    }
    
    static int[][] moveOfDir(int[][] map){
        int[][] newMap = new int[N][N];
        
        for(int x=0;x<N;x++){
            Deque<Block> dq = new ArrayDeque();
            for(int y=0;y<N;y++){
                if(!dq.isEmpty() && map[y][x] != 0 && dq.peekLast().num == map[y][x] && !dq.peekLast().crash){
                    dq.pollLast();
                    dq.offerLast(new Block(map[y][x]*2, true));
                }else if(map[y][x] != 0){
                    dq.offerLast(new Block(map[y][x], false));
                }
            }
            
            int y=0;
            while(!dq.isEmpty()){
                newMap[y++][x] = dq.pollFirst().num;
            }
        }
        
        return newMap;
    }

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

		return maxValue;
	}

	static class Block{
		int num;
		boolean crash;
		public Block(int num, boolean isCrash){
			this.num = num;
			crash = isCrash;
		}
	}
}

---

Result

---

Reference

https://velog.io/@hyunjong96/BOJ-%EC%8A%A4%ED%8B%B0%EC%BB%A4-%EB%B6%99%EC%9D%B4%EA%B8%B0