백준 - 12100. 2048 (Easy)

구현한 코드가 성능은 좋지 않지만 개인적으로 마음에 들어서 정리하고자 한다.

 

12100. 2048 (Easy)

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

 

 

접근

문제의 형태와 조건(시간제한이 1초, N의 최댓값이 20, 최대 이동 횟수가 5회)을 보고 구현&시뮬레이션이라고 생각하며 풀이를 시작했다.

 

이런 문제를 풀 때마다 성능이 우선이라고 생각해 코드가 마음에 들지 않아도 적당히만 손보고 넘어갔었다.

하지만 이 문제는 성능을 위해 상하좌우 이동 로직을 각각 구현하면 코드가 매우 유사하기에 매우 별로일 것이라고 생각했다.

 

따라서 이를 해결할 방법을 고민했고 그렇게 떠올린 해결책은 보드를 돌리는 것이다.

보드를 회전시키는 동작이 추가로 필요하지만 블록을 한 방향으로만 이동시켜도 문제를 풀 수 있어 코드가 깔끔할 것이라고 판단했다.

 

 

의문

"보드를 돌리면 답이 올바르게 나올까?"

 

아래 그림은 한 보드를 네 방향으로 이동시키는 경우이다. 이를 1번이라고 하자.

 

다음으로 아래 그림은 보드를 돌린 후 한 방향으로 이동시키는 경우이다. 이를 2번이라고 하자.

 

위의 그림들에선 1번과 2번의 이동 결과가 다르기에 동작이 다른 것 아니냐고 생각할 수 있지만

다음 동작에서 2번의 결과를 또다시 회전시키므로 1번과 2번의 동작 결과는 같다.

 

예를 들어 아래와 같이 2번 결과의 노란색 보드를 기준으로 생각해 보았을 때 

이를 다시 회전시키면 아래의 왼쪽 결과가 되며 이는 오른쪽과 같이 1번 결과의 두 번째 경우와 같다.

 

두 방법 모두 한 보드에 대해 4개의 다른 결과가 나오므로 경우의 수에 대해서도 잘못된 부분은 없다.

 

 

풀이 코드

아래는 구현 코드이다. 

 

Board 클래스는 이동 횟수와 보드를 가지고 있으며 회전된 4개의 보드를 리스트로 반환하는 역할을 한다.

Main에선 보드를 왼쪽으로 움직이고, 이동 횟수가 5이면 최댓값을 비교하는 역할을 한다.

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

public class Main {

    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[][] inputBoard = new int[N][N];
        for (int r = 0; r < N; r++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                inputBoard[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        Queue<Board> boards = new ArrayDeque<>();
        boards.add(new Board(inputBoard, 0));
        System.out.print(play(boards));
    }

    private static int play(Queue<Board> boards) {
        int answer = 0;
        while (!boards.isEmpty()) {
            Board board = boards.poll();
            if (board.count == 5) {
                answer = Math.max(getMaxNumber(board.board), answer);
                continue;
            }
            for (int[][] turnedBoard : board.getTurnedBoards()) {
                boards.add(move(new Board(turnedBoard, board.count + 1)));
            }
        }
        return answer;
    }

    private static Board move(Board board) {
        for (int r = 0; r < N; r++) {
            combinePerLine(board.board[r]);
        }
        return board;
    }

    private static void combinePerLine(int[] line) {
        boolean[] isMoved = new boolean[N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - (i + 1); j++) {
                if (line[j] == 0) {
                    line[j] = line[j + 1];
                    line[j + 1] = 0;
                    isMoved[j] = isMoved[j + 1];
                    isMoved[j + 1] = false;
                    continue;
                }

                if (line[j] == line[j + 1] && !isMoved[j] && !isMoved[j + 1]) {
                    line[j] *= 2;
                    line[j + 1] = 0;
                    isMoved[j] = true;
                }
            }
        }
    }

    private static int getMaxNumber(int[][] board) {
        int max = Integer.MIN_VALUE;
        for (int[] rows : board) {
            for (int cell : rows) {
                if (cell > max) {
                    max = cell;
                }
            }
        }
        return max;
    }

}

class Board {

    int count;
    int[][] board;

    Board(int[][] board, int count) {
        this.board = board.clone();
        this.count = count;
    }

    List<int[][]> getTurnedBoards() {
        List<int[][]> turnedBoards = new ArrayList<>();
        turnedBoards.add(board.clone());
        for (int i = 0; i < 3; i++) {
            turnedBoards.add(turnBoard(turnedBoards.get(i)));
        }
        return turnedBoards;
    }

    private int[][] turnBoard(int[][] inputBoard) {
        int N = board.length;
        int[][] turnedBoard = new int[N][N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                turnedBoard[r][c] = inputBoard[N - (c + 1)][r];
            }
        }
        return turnedBoard;
    }

}

 

후기

사실 보드를 회전시키는 로직이 추가로 들어가기 때문에 다른 사람들의 코드에 비해 속도가 빠르지는 않다.

하지만 메서드 재사용이 잘 되고 중복되는 코드가 없다는 점에서 만족스럽다.