[백준/JAVA] 12100번: 2048 (Easy)

📖 문제

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

 

 

 

💡  풀이 방식

• 백트래킹 + 시뮬레이션

 

백트래킹으로 상하좌우 4방향에 대해 5회까지 다 이동시켜보고, 배열 내 가장 큰 수를 구한다.

 

 

🔸 void DFS(명령 횟수)

[종료 조건] 명령 횟수가 5번인 경우, 배열 내 최댓값을 탐색하고, 이를 최댓값과 비교해 최댓값 갱신

if(cnt == 5) {
    findMax();
    return;
}

 

그게 아닌 경우, 과정 1,2를 진행한다.

 

1) 원본 배열 map을 복사한다.

int[][] copy = copyArray(map);

 

2) 상하좌우 4방향 중 이동 방향을 정하고, 해당 방향으로 이동시키고, 명령 횟수에 +1해 재귀호출을 진행한다. 그리고 이동시켰던 배열 값을 원상복구한다.

for(int d = 0 ; d < 4 ; d++) {
    move(d);
    dfs(cnt + 1);

    // 배열 값 원상복구
    map = copyArray(copy);
}

 

 

🔸 void move(이동 방향 숫자)

0:상, 1:하, 2:좌, 3:우를 나타낸다.

해당 방향으로 값을 끌어오고, 배열을 갱신한다.

 

🔸 void findMax()

배열 내 최댓값을 찾아 정답과 비교해 더 큰 값으로 정답을 갱신한다.

 

 

 

💥 유의사항

- 몰아넣기 후, 배열 원상 복구 해줘야 함

- 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] map;
    static int answer = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dfs(0);
        System.out.println(answer);
    }
    
    private static void dfs(int cnt) {
        // 명령 5번 수행 후 종료
        if(cnt == 5) {
            findMax();
            return;
        }
        
        // 배열 복사 (deep copy)
        int[][] copy = copyArray(map);
        
        // 이동 방향 정하기
        for(int d = 0 ; d < 4 ; d++) {
            move(d);
            dfs(cnt + 1);
            
            // 배열 값 원상복구
            map = copyArray(copy);
        }
    }
    
    // 배열 복사하는 함수
    private static int[][] copyArray(int[][] arr) {
        int[][] tmp = new int[N][N];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                tmp[i][j] = arr[i][j];
            }
        }
        return tmp;
    }
    
    // 해당 방향으로 이동하는 함수 (0:상 / 1:하 / 2:좌 / 3:우)
    private static void move(int dir) {
        switch(dir) {
            // [상]
            case 0:
                for(int i = 0 ; i < N ; i++) {  // 열
                    int idx = 0;    // 값 넣을 위치
                    int block = 0;  // 최근 블록의 값
                    
                    for(int j = 0 ; j < N ; j++) {  // 행
                        if(map[j][i] != 0) {    // 현재 블록 값이 0이 아닌 경우
                            if(block == map[j][i]) {            // 최근 블록 값이 현재 블록 값과 "같다면"
                                map[idx - 1][i] = block * 2;    // 블록 합치기
                                block = 0;                      // 블록 합쳐졌으므로 0으로 갱신
                                map[j][i] = 0;                  // 값 합쳤으므로 현재 블록 값을 0으로 갱신
                            }
                            else {
                                block = map[j][i];              // 블록 변수 값을 현재 블록 값으로 갱신
                                map[j][i] = 0;                  // 현재 블록 값 0으로 바꿈
                                map[idx][i] = block;            // 값 넣을 위치에 최근 블록 값 넣기
                                idx++;
                            }
                        }
                    }
                }
                break;
            
            // [하]
            case 1:
                for(int i = 0 ; i < N ; i++) {  // 열
                    int idx = N-1;  // 값 넣을 위치
                    int block = 0;  // 최근 블록의 값
                    
                    for(int j = N-1 ; j >= 0 ; j--) {   // 행
                        if(map[j][i] != 0) {
                            if(block == map[j][i]) {
                                map[idx + 1][i] = block * 2;
                                block = 0;
                                map[j][i] = 0;
                            }
                            else {
                                block = map[j][i];
                                map[j][i] = 0;
                                map[idx][i] = block;
                                idx--;
                            }
                        }
                    }
                }
                break;
            
            // [좌]
            case 2:
                for(int i = 0 ; i < N ; i++) {  // 행
                    int idx = 0;    // 값 넣을 위치
                    int block = 0;  // 최근 블록의 값
                    
                    for(int j = 0 ; j < N ; j++) {  // 열
                        if(map[i][j] != 0) {
                            if(block == map[i][j]) {
                                map[i][idx - 1] = block * 2;
                                block = 0;
                                map[i][j] = 0;
                            }
                            else {
                                block = map[i][j];
                                map[i][j] = 0;
                                map[i][idx] = block;
                                idx++;
                            }
                        }
                    }
                }
                break;
            
            // [우]
            case 3:
                for(int i = 0 ; i < N ; i++) {  // 행
                    int idx = N-1;  // 값 넣을 위치  
                    int block = 0;  // 최근 블록의 값
                    
                    for(int j = N-1 ; j >= 0 ; j--) {   // 열
                        if(map[i][j] != 0) {
                            if(block == map[i][j]) {
                                map[i][idx + 1] = block * 2;
                                block = 0;
                                map[i][j] = 0;
                            }
                            else {
                                block = map[i][j];
                                map[i][j] = 0;
                                map[i][idx] = block;
                                idx--;
                            }
                        }
                    }
                }
                break;
        }
    }
    
    // 최댓값 찾는 함수
    private static void findMax() {
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(map[i][j] > answer) {
                    answer = map[i][j];
                }
            }
        }
    }
}
 

 

 

➕ 다른 풀이 방식

합쳐진 곳을 또 방문할 수 없게 방문 표시 배열을 사용하셨다,,,,

이게 개인적으로 몰아넣기 하는 부분 함수로 처리하셔서 중복되는 코드도 적고 더 이해하기 좋은 듯,,  ✅

[백준 12100] 2048(Easy) (자바)

 private static void move(int x, int y, int dir) {
    if (temp[x][y] == 0) {
        return;
    }

    while (true) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx < 1 || ny < 1 || nx > n || ny > n)	return;
        if (visit[nx][ny])	return;

        if (temp[nx][ny] == temp[x][y]) {
            //같을 때 합치기
            visit[nx][ny] = true;
            temp[nx][ny] *= 2;
            temp[x][y] = 0;
            return;
        } else if (temp[nx][ny] != 0) {
            //같지 않고 다른 수가 있을 때 못 합침
            return;
        }

        temp[nx][ny] = temp[x][y];
        temp[x][y] = 0;
        x = nx;
        y = ny;
    }

}

 

---

💦 어려웠던 점

- 블록을 몰아 넣고 합치는 과정이 인덱스가 헷갈리고 어려웠다,,,,,ㅠ

 

 

🧐 새로 알게 된 내용

- 몰아넣기 방법,,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[백준 12100] 2048 (Easy) (자바)

[백준] 12100: 2048 (Easy) (Java)