[백준 java] 12100-2048(Easy)

12100번: 2048 (Easy)

 

 

1. 4방향 움직임이 가능하다

int[][] D = {{-1,0},{1,0},{0,-1},{0,1}}; //상하좌우

2. 두 블록 충돌하면 하나로 합쳐진다

새로운 좌표(이동하려는 좌표) nr cr 값이 r c 와 같다면 

nr cr 좌표 값 * 2를 저장하고 r c 좌표값은 0으로 지정한다

3. 이미 이동한 블럭은 합쳐지지않는다 

boolean으로 합쳐진 부분은 true처리

boolean이 false인곳만 합치게한다

 

4. 똑같은 수가 3개있는 경우는 이동하려는 칸이 합쳐짐

위로 이동하면 위에있는 같은수가 합쳐진다

따라서 아래와 같은 순서로 순회하며 이동시킨다

 

상측이동 - 0,0부터4,4   (i=0)
하측이동 - 4,4부터 0,0   (i=1)
좌측이동 - 0,0부터4,4   (i=2)
우측이동 - 4,4부터 0,0   (i=3)

 

따라서 if문으로 두가지로 나눠서 순회한다

i가 0과 2일때는 for문을 0부터 4까지 돌리고

i가 1과 3일때는 4부터 0까지 돌린다

 

이제 move에서 순서를 정하면

move21에서 이동하는 동작을 수행한다 (이름은 아무거나 막 지엇다...)

 

move21에서 동작이 있으면(움직이면) isMove = true로 변경하고

움직임이 있으면(isMove) 큐에 이동시킨 board를 저장한다

자세한 설명은 아래 코드의 주석참고

 

 

주의해야할점!

for문을 사용하여 상하좌우를 탐색할때 (같은move단계에서) 2차원 배열을 계속 초기화 해주기

초기값에서 상 하 좌 우 를 각각 탐색해야하는데 만약 초기화 해주지 않으면

초기값 > 상측 탐색 > 상측 탐색한 값으로 다시 하측 탐색 이런식으로 수행된다

 

 

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

public class B12100 {
    static int N;
    static int maxInt=0;
    static int[][] firstBoard;
    static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}}; //상하좌우


    static class Board{
        int[][] Board;
        int move;
        Board(int[][] board, int m){
            Board = board;
            move = m;
        }
        public int[][] getBoard(){
            return Board;
        }
    }

    private static int[][] move21(int[][] board, int r, int c,  int i, boolean[][] isAdd) {
    	//만약 현재좌표 값이 0이들어왔다면 리턴
        if(board[r][c] == 0) return board;
        
        //새로운 좌표 구하기
        //i값이 0,1,2,3 순서대로 상 하 좌 우
        int nr = r+D[i][0];
        int nc = c+D[i][1];

		//보드의 범위를 벗어났을때
        if(nr<0 || nr>=N || nc<0 || nc>=N){
            return board;
        }
        
		// 만약 이동하려는 칸의 숫자가 지금 좌표와 같은값이고
        // 이동하려는 칸의 좌표가 합쳐지지 않은 상태라면
        if(!isAdd[nr][nc] && board[nr][nc] == board[r][c]){
            //합치고 원래있던 자리는 비우기
            isAdd[nr][nc] = true;
            board[nr][nc] *=2;
            board[r][c] = 0;

            if(board[nr][nc]>maxInt){
                maxInt = board[nr][nc];
            }
            return board;
        }

		//이동하려는 칸에 숫자가 있으면 끝 (합치는건 위에서 했으니)
        if(board[nr][nc]>0 ) return board;

		//만약 이동하려는 칸이 비어있으면 이동
        if(board[nr][nc]==0){
            board[nr][nc] = board[r][c];
            board[r][c] = 0;
            return move21(board, nr, nc, i, isAdd);
        }

        return null;
    }

    private static void move() {
        Queue<Board> q = new LinkedList<>();
        q.add(new Board(firstBoard,0));

        while(!q.isEmpty()){
            Board temp = q.remove();
            if(temp.move >= 5) continue;

            //최대 5번 이동
                for (int i = 0; i < 4; i++) {
                    // 0 : 상측이동
                    // 1 : 하측이동
                    // 2 : 좌측이동
                    // 3 : 우측이동
                    boolean[][] isAdd = new boolean[N][N];
                    boolean isMove = false;
                    int[][] newBoard = new int[N][N];
                    
					
                    //2차원 배열 초기화
                    for(int v=0; v<N; v++) {
                        for(int w=0; w<N; w++) {
                            newBoard[v][w] =temp.getBoard()[v][w];
                        }
                    }

					//상, 좌측 탐색
                    if (i == 0 || i == 2) {
                        for (int r = 0; r < N; r++) {
                            for (int c = 0; c < N; c++) {
                                if(newBoard[r][c]==0) continue;
                                int[][] num = move21(newBoard,r,c,i, isAdd);
                                if(num == null) {
                                    continue;
                                }
                                newBoard = num;
                                isMove = true;
                            }
                        }
                        //아래 주석은 어떻게 이동하는지 보고싶으면
                    	//     System.out.println(Arrays.deepToString(newBoard));
                   		//        System.out.println("test : " + i + " move : "+(temp.move+1));
                        if(isMove) q.add(new Board(newBoard, temp.move+1));
                    }

					//하, 우측 탐색
                    if (i == 1 || i == 3) {
                        for (int r = (N-1); r >= 0; r--) {
                            for (int c = (N-1); c >= 0; c--) {
                                if(newBoard[r][c]==0) continue;
                                int[][] num  = move21(newBoard,r,c,i,isAdd);
                                if(num == null) {
                                    continue;
                                }
                                newBoard = num;
                                isMove = true;
                            }
                        }
                        //아래 주석은 어떻게 이동하는지 보고싶으면
                        //    System.out.println(Arrays.deepToString(newBoard));
                        //    System.out.println("test : " + i + " move : "+(temp.move+1));
                        if(isMove) q.add(new Board(newBoard, temp.move+1));
                    }
                }
            }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        firstBoard = new int[N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                firstBoard[i][j] = sc.nextInt();
                //최대값 지정
                if(firstBoard[i][j]>maxInt) maxInt = firstBoard[i][j];
            }
        }
        move();
        System.out.println(maxInt);
    }
}

 

 

쉬운 문제라면서 쉽지않았다..