[BOJ] 백준 12100 2048(Easy) - Python/Java

문제

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

12100번: 2048 (Easy)

 

해설

배열의 회전이나 변환, 슬라이싱을 얼마나 잘할 수 있는지를 보는 문제 같았습니다.

 

문제에서 요구하는 시뮬레이션 상황을 구현하기 위해서는 배열의 원소들을 상하좌우로 미는 함수를 구현해야 하는데요.

 

배열을 적절히 인덱싱해서 상하좌우에 해당하는 함수를 각각 구현할 수도 있지만, 저는 왼쪽으로 미는 함수 하나만 구현해놓고 배열의 전치(Transpose)와 대칭(Mirroring)을 이용해 문제를 해결했습니다.

 

예를 들어, 배열의 원소들을 위로 밀어주는 작업을 해야 한다고 하면 이차원 배열을 Transpose 한 뒤 왼쪽으로 밀어주고, 다시 Transpose 시켜서 원래 형태로 바꿔주는 것이죠.

 

Transpose와 Mirroring을 구현하는 것은 크게 어렵지 않으니 코드를 참고해주시면 감사하겠습니다.

 

마지막으로 왼쪽으로 미는 함수 자체는 스택을 살짝 이용했습니다. 어차피 현재 구현해야 하는 것은 왼쪽으로 원소들을 밀면서 합치는 것이기 때문에 스택에 원소를 하나씩 넣으면서 스택의 맨 마지막값과 현재 넣을 값을 비교하는 식으로 생각했습니다. 그리고 이미 합쳐진 블록을 판단할 때는 combinedBlock 이라는 Boolean 변수 하나로 관리했습니다.

 

문제는 꽤 복잡하지만, 해야하는 일은 단순했기 때문에 아래 코드를 보면 이해되실 것 같습니다.

풀이 - 파이썬

import copy
n = int(input())

def transpose(grid): # 배열 뒤집기
    return list(map(list, zip(*grid)))

def mirroring(grid): # 좌우 대칭
    n = len(grid)
    for i in range(n):
        grid[i] = grid[i][::-1]
    return grid

def pushBlocksToLeft(grid): # 왼쪽으로 밀기
    n = len(grid)
    for i in range(n):
        stack = []
        combinedBlock = False
        for j in range(n):
            if grid[i][j] == 0: continue # 빈칸
            if len(stack) == 0: # 스택이 비어있으면 삽입
                stack.append(grid[i][j])
            else:
                if stack[-1] == grid[i][j]: # 값이 동일하고 합쳐진 블록이 아닐 때
                    if not combinedBlock:
                        stack.pop()
                        stack.append(2*grid[i][j])
                        combinedBlock = True
                    else:
                        stack.append(grid[i][j])
                        combinedBlock = False

                else:
                    stack.append(grid[i][j])
                    combinedBlock = False

        while len(stack) < n: # 보드의 크기와 스택의 크기 맞추기
            stack.append(0)
        for k in range(n):
            grid[i][k] = stack[k]
    return grid


def moveBlocks(grid, direction, count):
    global answer
    temp = copy.deepcopy(grid)
    if count == 5: # 5회 이동 후 최대값 리턴
        answer = max(answer, max(map(max, grid)))
        return

    if direction == 0: # 왼쪽으로 밀기
        temp= pushBlocksToLeft(temp)

    if direction == 1: # 오른쪽으로 밀기 = 좌우대칭하고 왼쪽으로 밀고 원상복구
        temp = mirroring(temp)
        temp = pushBlocksToLeft(temp)
        temp = mirroring(temp)

    if direction == 2: # 위로 밀기
        temp = transpose(temp)
        temp = pushBlocksToLeft(temp)
        temp = transpose(temp)

    if direction == 3: # 아래로 밀기
        temp = transpose(temp)
        temp = mirroring(temp)
        temp = pushBlocksToLeft(temp)
        temp = mirroring(temp)
        temp = transpose(temp)

    for direction in range(4):
        moveBlocks(temp, direction, count+1)



# 초기 블록의 값과 합쳐진 여부를 나타내는 리스트 생성
grid = [list(map(int, input().split())) for _ in range(n)]
answer = 0
for i in range(4): # 네 방향에 대해 시작
    moveBlocks(grid, i, 0) 
print(answer)

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class B_12100 {
    static int[][] grid;
    static int answer = 0;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        grid = new int[n][n];
        for(int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < 4; i++) moveBlocks(grid, i, 0);
        System.out.println(answer);
    }

    public static void moveBlocks(int[][] grid, int dir, int count){
        if(count == 5){
            answer = Math.max(answer, getMaxValue(grid));
            return;
        }
        int[][] temp = deepCopy(grid);

        switch (dir){
            case 0:
                temp = pushBlocksToLeft(temp);
                break;
            case 1:
                temp = mirroring(temp);
                temp = pushBlocksToLeft(temp);
                temp = mirroring(temp);
                break;
            case 2:
                temp = transpose(temp);
                temp = pushBlocksToLeft(temp);
                temp = transpose(temp);
                break;
            case 3:
                temp = transpose(temp);
                temp = mirroring(temp);
                temp = pushBlocksToLeft(temp);
                temp = mirroring(temp);
                temp = transpose(temp);
                break;
        }
        for(int i = 0; i < 4; i++){
            moveBlocks(temp, i, count+1);
        }
    }

    public static int[][] transpose(int[][] grid){
        int[][] result = new int[n][n];
        for (int i=0; i < n; i++) {
            for (int j=0; j < n; j++) {
                result[j][i] = grid[i][j];
            }
        }
        return result;
    }

    public static int[][] mirroring(int[][] grid){
        int[][] result = new int[n][n];
        for (int i=0; i < n; i++) {
            for (int j=0; j < n; j++) {
                result[i][n-j-1] = grid[i][j];
            }
        }
        return result;
    }

    public static int[][] pushBlocksToLeft(int[][] grid){
        for(int i = 0; i < n; i++){
            Stack<Integer> stack = new Stack<>();
            boolean combinedBlock = false;
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 0) continue;
                if(stack.isEmpty()) stack.add(grid[i][j]);
                else{
                    if(stack.peek() == grid[i][j]){
                        if(!combinedBlock){
                            stack.pop();
                            stack.add(2*grid[i][j]);
                            combinedBlock = true;
                        }else{
                            stack.add(grid[i][j]);
                            combinedBlock = false;
                        }
                    }else{
                        stack.add(grid[i][j]);
                        combinedBlock = false;
                    }
                }
            }
            while(stack.size() < n) stack.add(0);
            for(int k = 0; k < n; k++){
                grid[i][k] = stack.get(k);
            }
        }
        return grid;
    }

    public static int getMaxValue(int[][] grid){
        int result = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] > result)
                    result = grid[i][j];
            }
        }
        return result;
    }

    public static int[][] deepCopy(int[][] grid){
        int[][] result = new int[n][n];
        for(int i = 0; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                result[i][j] = grid[i][j];
            }
        }
        return result;
    }

}