[Algorithm] SW 기출문제 - 2048 (Easy) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 SW 기출문제 - 2048(Easy)를 해결한 과정을 정리하고자 합니다.!

 

문제 출처: https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

 

1. 풀이 소스:

 

package sw_12100.success;

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = parseInt(br.readLine());

        Board board = new Board(n);

        for (int i = 0 ; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                board.setBoard(i, j, parseInt(st.nextToken()));
            }
        }
        board.dfs(0);
        System.out.println(board.getAnswer());
    }
}

class Board {

    static final char[] DIR = {'U', 'D', 'L', 'R'}; // up, down, left, right

    int n;
    int answer;
    int[][] map;

    Board (int n) {
        this.n = n;
        map = new int[n][n];
    }

    void setBoard(int x, int y, int v) {
        map[x][y] = v;
    }

    int getAnswer() {
        return this.answer;
    }

    // dfs로 최대 5번 반복되는 과정에서 최대값 찾기
    void dfs(int step) {
        if (step == 5) { // count가 5라면 최대값 찾기
            for (int[] mapRow : map) {
                for (int num : mapRow) {
                    answer = Math.max(answer, num);
                }
            }
            return;
        }

        int[][] clone = new int[n][n];
        for (int i = 0; i < n; i++) {
            clone[i] = map[i].clone();
        }

        for (int i = 0; i < DIR.length; i++) { // 상 하 좌 우
            moveBlock(DIR[i]); // 블록 움직이기
            dfs(step + 1); // step 증가시켜서 다음 step 진행

            for (int j = 0; j < n; j++) map[j] = clone[j].clone();
        }
    }

    // block의 역할 --> 미는 블록이 두번 합쳐지더라도 다음 block을 0으로 만들어 세번 겹치지 않도록 보호
    void moveBlock(char dir) {
        if (dir == 'U') { // 블록을 위로 몰기 (낮은 행으로 몰기)
            for (int c = 0; c < n; c++) { // 선택된 맵의 열 (col)
                int row = 0;
                int block = 0;
                for (int r = 0; r < n; r++) { //선택된 맵의 행 (row)
                    if (map[r][c] != 0) { // 0이 아니라면 블록이 있음
                        if (map[r][c] == block) { // 블록과 선택한 블록이 같다면
                            map[row - 1][c] = block * 2; // 낮은 행으로 합치기
                            map[r][c] = 0; // 선택된 맵 위치 블록 0
                            block = 0; // 그 위치에 있는 블록 0
                        }

                        // 만약 r = 1, c = 1, row = 0 인 경우, 앞에 블록이 없으므로
                        // r = 0인 경우 map[r][c] != 0 통과, block은 0이 유지되므로
                        // 자연스럽게 블록이 없는 공간에 밀어넣게 됨 이후 row++
                        else {
                            block = map[r][c]; // 현재위치 블록 설정
                            map[r][c] = 0; // r, c 위치 0으로 설정하기
                            map[row][c] = block; // 위로 밀어서 블록 값을 위치 시키기 (이 경우 제자리에 위치할 수 있으므로 map[r][c]보다 뒤에 있어야 함!!!
                            row++; // 다음 밀 곳은 한 칸 아래로 내린 곳
                        }
                    }
                }
            }
        }

        else if (dir == 'D') { // 블록을 아래로 몰기
            for (int c = 0; c < n; c++) {
                int row = n - 1; // 처음으로 옮겨져야 하는 도착 위치는 마지막 행
                int block = 0;
                for (int r = n - 1; r >= 0; r--) {
                    if (map[r][c] != 0) {
                        if (map[r][c] == block) {
                            map[row + 1][c] = block * 2;
                            map[r][c] = 0;
                            block = 0;
                        }

                        else {
                            block = map[r][c];
                            map[r][c] = 0;
                            map[row][c] = block;
                            row--; // 다음 번 블록은 맨 아래 위치에서 한 칸 올린 곳
                        }
                    }
                }
            }
        }

        else if (dir == 'L') { // 블록을 왼쪽으로 몰기
            for (int r = 0; r < n; r++) {
                int col = 0; // 옮겨질 위치의 열
                int block = 0;
                for (int c = 0; c < n; c++) {
                    if (map[r][c] != 0) {
                        if (map[r][c] == block) {
                            map[r][col - 1] = block * 2;
                            map[r][c] = 0;
                            block = 0;
                        }
                        else {
                            block = map[r][c];
                            map[r][c] = 0;
                            map[r][col] = block;
                            col++;
                        }
                    }
                }
            }
        }

        else if (dir == 'R') { // 블록을 오른쪽으로 몰기
            for (int r = 0; r < n; r++) {
                int col = n - 1;
                int block = 0;
                for (int c = n - 1; c >= 0; c--) {
                    if (map[r][c] != 0) {
                        if (map[r][c] == block) {
                            map[r][col + 1] = block * 2;
                            map[r][c] = 0;
                            block = 0;
                        }

                        else {
                            block = map[r][c];
                            map[r][c] = 0;
                            map[r][col] = block;
                            col--;
                        }
                    }
                }
            }
        }
    }
}

 

 

2. 풀이 과정:

 

해당 문제는, 블록을 최대 5번까지 이동시킨 후, 블록에 최댓값을 구하는 것입니다. 최대 5번이므로 3번 4번에서도 최댓값이 나올 수 있지만, 블록을 합치는 것은 x, y 좌표에 대한 값 V는 증가함수 형태이므로 (양수의 값을 합치므로) 5번을 실행한 후 최댓값을 계산하면 중간 계산 과정을 생략할 수 있습니다.

 

배열 복제

제가 계속 실수 했던 부분은 배열 복제 부분입니다. map.clone()을 하게 되면 1차원 배열은 값이 복사되어 다른 배열을 생성할 수 있습니다. 하지만 map이 2차원 배열인 경우 참조를 복사하므로 '얕은 복사'가 수행되게 됩니다.

 

int[][] clone = new int[n][n];
for (int i = 0; i < n; i++) {
    clone[i] = map[i].clone();
}

 따라서, 다음과 같이 for문으로 1차원 배열 단위로 clone()하여 값이 복사될 수 있도록 처리해야 합니다.

 

헷갈리는 상 하 좌 우

상 하 좌 우를 처리하다보면 수학은 보통 (0, 0)이 아래에 위치합니다. 하지만 데이터베이스나 이러한 map 문제를 해결해야 할 때는 (0, 0) 혹은 (1, 1)이 왼쪽 상단에 위치하는 경우가 많습니다. 따라서, 행을 내려야 할 때, 혹은 행을 올려야 할 때 
Down 작업은 row++, Up 작업은 row-- 하는 것이 필요합니다.

 

이전에 i, j를 쓸 때는 이 과정이 너무 헷갈려서 추후 풀 때는, r, c로 설정하여 헷갈림이 덜 하도록 구현하였습니다.

 

 

블록 밀기

 

블록을 미는 과정에서 아래와 같은 소스가 있습니다. 해당 소스는 풀이 소스에 자세하게 주석처리 하였지만, 중요한 포인트는 block의 쓰임새입니다. 

 

for (int r = 0; r < n; r++) {
    int col = n - 1;
    int block = 0;
    for (int c = n - 1; c >= 0; c--) {
        if (map[r][c] != 0) {
            if (map[r][c] == block) {
                map[r][col + 1] = block * 2;
                map[r][c] = 0;
                block = 0;
            }

            else {
                block = map[r][c];
                map[r][c] = 0;
                map[r][col] = block;
                col--;
            }
        }
    }
}

 

열을 오른쪽으로 민다고 하는 것은 n - 1에서 시작해서 n - 2 -> n - 1 / n - 3 -> n -2 -> n - 1 (가능하다면) 이러한 방식으로 
밀어야 하는 곳의 가까운 곳에서부터 블록을 합쳐야 합니다.

 

만약 밀고자 하는 곳에서 값이 0이 아니라는 것은 블록이 있다는 것을 의미하고,

해당 위치가 블록의 값과 같다면 블록에 2배를 합니다.

 

이 후, 블록을 0으로 설정하는데, 이는 무조건 다음 혹은 이후에 실행되는 반복에서 아래의 코드가 실행되는 것을 방지합니다.

 

map[r][c] != 0 && map[r][c] == block

블록이 0이 되어 있으므로 map[r][c]가 == 0이라면 다음 반복으로 넘어가므로, 블록이 값을 가져야만 해당 구문이 실행될 수 있습니다. 따라서, 새로운 값으로 블록을 생성해야 하므로, 블록을 미는 과정에서 3번 이상 겹치는 일이 발생하지 않습니다.

 

 

이상으로 2048 문제 풀이를 마치도록 하겠습니다.! 감사합니다 !!