알고리즘 풀이 - 백준 12100(2048 (Easy), 완전 탐색(시뮬레이션))

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

2048 게임 문제. 5번의 이동으로 얻을 수 있는 최대 큰 블록을 출력하는 문제

 

 

2. 풀이

 

이 문제는 시뮬레이션으로 해결하였다. 실제 모든 블록을 이동시켜 가면서 최대 값을 구하여 출력하는 문제이다. 시뮬레이션은 구현이 까다롭기에 푸는데 오래 걸렸다.

기본적으로 재귀를 통해 5번을 모두 이동시키고 이동이 끝났으면 최대값을 찾도록 한다.

 

이동하여 블록들을 위치시키는 것이 조금 구현에 까다롭다. 우선 아래의 그림을 통해 이해해보자.

아래의 예시에서는 동쪽으로만 이동시키는 경우를 통해 알아보자. 현재 Row / Column은 2중 반복문을 통해 각 Row, Column를 순회 중임을 표시하기 위해 설정 했다.

 

우선 좌측 그림은 초기 상태라고 가정하자. 2중 반복문을 통해 Row는 0부터, Column은 가장 끝에서부터(여기선 3) 순회를 시작한다.

이 때, index 변수는 다음 블록을 놓을 Column 위치 값이며, block 변수는 합쳐지지 않은 가장 최근에 검사한 Column의 블록 값이다.(초기에는 index는 방향에 따라 0또는 n-1, block은 0으로 초기화한다.)

그럼 우측 사진을 보자. 좌측의 Column에서는 아무 값이 없으니 0이므로 그냥 넘어간다. 그 뒤, 1칸 좌측으로 이동하여 블록이 있는지를 검사한다. 해당 위치에는 2라는 블록이 있다.

이 때, 현재 block 변수의 값과 이 위치의 블록 값이 같다면 둘은 더할 수 있다! 그런데, 현재 block 값은 0이므로 현재 블록만 index 위치로 옮겨주고 index 값을 1 빼주면 된다.

그리고, 현재 블록은 덧셈에 사용되지 않았으므로 block 변수에 저장한다!

 

다음 그림을 보자.

좌측 그림에선, 3번째 Column(인덱스 값으로는 2)까지 검사했으니 2번째 Column을 조사할 차례이다. 위 그림에선 이미 결과를 보여줘서 그런데 원래 2번째 Column에는 2라는 값이 있었다.

그러므로, 현재 block에 저장되었던 값은 2였는데 해당 값과 일치하므로 둘은 더할 수 있다. 따라서 4로 저장하고 현재 Column의 값은 0으로 바꾸어 준다.

또한, 덧셈을 수행했으므로 index 변수는 바뀔 필요가 없으나, block은 가장 최근에 덧셈에 사용된 숫자가 없으니 0으로 다시 바꾸어 준다.

 

마지막으로 우측 그림을 보면, 마지막으로 가장 왼쪽의 Column을 체크하는데 여기에는 원래 4가 있었다. 그런데 현재 block 변수 값이 0이므로 더할 수는 없다.

따라서 현재 index 변수의 값으로 이동시키고 index를 1 빼준 뒤, block 변수에 현재 값을 넣어주면 된다.(물론 더 이상 탐색할 Column이 없어 덧셈에 사용할 수는 없다.)

이 과정을 모든 Row에서 반복하여 이동을 완료시킨다.

 

 

위의 예시에서는 우측으로 이동시키는 경우만 체크했지만, 각 방향에 따라 전체 로직은 동일하더라도 초기 변수 초기화 및 이동 방향 등이 다르므로 그것을 고려하여 코드를 작성하면 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;
import java.util.*;

public class Main{
    static int n;
    static int[][] board;
    static int max = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        board = new int[n][n];
        
        for(int i=0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < n; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        game(0, board);
        System.out.println(max);
        br.close();
    }
    
    // cnt는 이동한 횟수, map은 현재 이동한 뒤의 2048 블록들의 상태값을 저장한 배열
    private static void game(int cnt, int[][] map){
    
        // 5번 이동했다면 전체 map에서 최대값을 찾고 반환
        if(cnt == 5){
            findMax(map);
            return;
        }
        
        // 현재 map을 그대로 사용하면 값이 바뀌므로 copy해서 해당 배열에서 이동을 시킨다.
        int[][] copy = new int[n][n];
        for(int i=0; i < n; i++){
            copy[i] = map[i].clone();
        }
        
        // 1, 2, 3, 4를 통해 각 방향으로 copy 배열을 이동시킨다.
        for(int i=1; i <= 4; i++){
            move(i, copy);
            
            // 이동 횟수를 추가하고 copy 배열을 전달한다.
            game(cnt+1, copy);
            
            // 전달되며 이동한 경우 다음 이동 때 다시 사용할 수 없으므로 다시 복사한다.
            for(int j=0; j < n; j++){
                copy[j] = map[j].clone();
            }
        }
    }
    
    // 2048에서 실제 블록을 이동시키는 함수
    private static void move(int dir, int[][] map){
        // 동쪽으로 이동
        if(dir == 1){
            for(int row=0; row < n; row++){
                int index = n-1;
                int block = 0;
                for(int col=n-1; col >= 0; col--){
                    if(map[row][col] != 0){
                        if(block == map[row][col]){
                            map[row][index+1] = block*2;
                            block = 0;
                            map[row][col] = 0;
                        } else {
                            block = map[row][col];
                            map[row][col] = 0;
                            map[row][index] = block;
                            index--;
                        }
                    }
                }
            }
        // 서쪽으로 이동
        } else if(dir == 2){
            for(int row=0; row < n; row++){
                int index = 0;
                int block = 0;
                for(int col=0; col < n; col++){
                    if(map[row][col] != 0){
                        if(block == map[row][col]){
                            map[row][index-1] = block*2;
                            block = 0;
                            map[row][col] = 0;
                        } else {
                            block = map[row][col];
                            map[row][col] = 0;
                            map[row][index] = block;
                            index++;
                        }
                    }
                }
            }
        // 남쪽으로 이동
        } else if(dir == 3){
            for(int col=0; col < n; col++){
                int index = n-1;
                int block = 0;
                for(int row=n-1; row >= 0; row--){
                    if(map[row][col] != 0){
                        if(block == map[row][col]){
                            map[index+1][col] = block*2;
                            block = 0;
                            map[row][col] = 0;
                        } else {
                            block = map[row][col];
                            map[row][col] = 0;
                            map[index][col] = block;
                            index--;
                        }
                    }
                }
            }
        // 북쪽으로 이동
        } else {
            for(int col=0; col < n; col++){
                int index = 0;
                int block = 0;
                for(int row=0; row < n; row++){
                    if(map[row][col] != 0){
                        if(block == map[row][col]){
                            map[index-1][col] = block*2;
                            block = 0;
                            map[row][col] = 0;
                        } else {
                            block = map[row][col];
                            map[row][col] = 0;
                            map[index][col] = block;
                            index++;
                        }
                    }
                }
            }
        }
    }
    
    // 최대값을 찾는 메소드
    private static void findMax(int[][] map){
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                if(map[i][j] > max){
                    max = map[i][j];
                }
            }
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.