[SWEA/Java] 6109. 추억의 2048게임

[SWEA/Java] 6109. 추억의 2048게임

SW Expert Academy

---

문제 해석

이 문제는 2048 게임의 변형으로, 게임 보드에서 주어진 방향으로 블록을 이동시키고 합치는 과정을 시뮬레이션하는 문제이다. 입력으로는 보드의 크기 𝑁N과 이동할 방향 𝑆S가 주어진다. 𝑆S는 'l' (왼쪽), 'r' (오른쪽), 'u' (위쪽), 'd' (아래쪽) 중 하나이다. 보드에는 숫자가 적힌 타일이 있으며, 이 타일들을 𝑆S에 따라 이동시키고 같은 숫자의 타일이 만나면 합쳐진다. 합쳐진 타일은 더 이상 합쳐질 수 없다.

풀이 과정

제출된 코드는 주어진 방향에 따라 타일들을 합치고 이동시키는 로직을 구현하고 있다. 각 방향에 따라 다른 메소드(goLeft, goRight, goUp, goDown)를 호출한다. 이 메소드들은 다음과 같은 과정을 수행한다

 

1. 같은 숫자의 타일이 인접해 있으면 합치고, 이미 합쳐진 타일에 대해서는 isMerged 배열을 사용하여 중복 합치기를 방지한다.
2. 타일을 주어진 방향으로 밀어내어 빈 공간을 없앤다.

 

이러한 과정은 각 방향에 대해 별도의 로직을 가진다. 예를 들어, 왼쪽으로 밀 때는 각 행을 왼쪽으로 탐색하며 같은 숫자의 타일을 합치고, 다시 한 번 탐색하여 0이 아닌 타일을 왼쪽으로 이동시킨다.

코드

package edu.ssafy.im.SWEA.D4.No6109;

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

public class Solution {
    private int N; // 보드의 크기
    private char S; // 이동할 방향
    private int[][] map; // 게임 보드의 현재 상태
    private boolean[][] isMerged; // 합쳐진 타일의 상태를 추적
    private StringBuilder sb = new StringBuilder(); // 결과를 출력하기 위한 StringBuilder

    public static void main(String[] args) throws IOException {
        new Solution().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken()); // 보드의 크기 N
            S = st.nextToken().charAt(0); // 이동 방향 S

            map = new int[N][N]; // 게임 보드 초기화
            isMerged = new boolean[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());
                }
            }

            sb.append("#").append(t).append("\n");
            sol(); // 게임 로직 처리
        }
        bw.write(sb.toString()); // 결과를 출력
        bw.flush();
        bw.close();
    }

    private void sol() {
        switch (S) {
            case 'l': goLeft(); break;
            case 'r': goRight(); break;
            case 'u': goUp(); break;
            case 'd': goDown(); break;
        }
        print(); // 보드 상태 출력
    }

    private void print() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
    }
    
    /*
    바뀌는 방향 기준으로 바깥 인덱스에서 안쪽 인덱스 순서대로 탐색
    1.
    같은 숫자일 경우 합치면서, 방문 체크 후 바깥 인덱스 값 0 처리
    탐색 중 사이에 0이 껴있다면 계속 탐색, 만약 0이 아니면 서로 다른 숫자이므로 탐색 종료
    2.
    숫자가 다 합쳐졌으므로 해당 방향으로 쭉 밀기
     */

    private void goLeft() {
        for (int x = 0; x < N; x++) {
            for (int y = 1; y < N; y++) {
                for (int ny = y - 1; ny >= 0 && map[x][ny] == 0; ny--) {
                    map[x][ny] = map[x][ny + 1];
                    map[x][ny + 1] = 0;
                }
                if (ny >= 0 && map[x][ny] == map[x][y] && !isMerged[x][ny]) {
                    map[x][ny] *= 2;
                    map[x][y] = 0;
                    isMerged[x][ny] = true;
                }
            }
        }
    }

    private void goRight() {
        for (int x = 0; x < N; x++) {
            for (int y = N - 2; y >= 0; y--) {
                for (int ny = y + 1; ny < N && map[x][ny] == 0; ny++) {
                    map[x][ny] = map[x][ny - 1];
                    map[x][ny - 1] = 0;
                }
                if (ny < N && map[x][ny] == map[x][y] && !isMerged[x][ny]) {
                    map[x][ny] *= 2;
                    map[x][y] = 0;
                    isMerged[x][ny] = true;
                }
            }
        }
    }

    private void goUp() {
        for (int y = 0; y < N; y++) {
            for (int x = 1; x < N; x++) {
                for (int nx = x - 1; nx >= 0 && map[nx][y] == 0; nx--) {
                    map[nx][y] = map[nx + 1][y];
                    map[nx + 1][y] = 0;
                }
                if (nx >= 0 && map[nx][y] == map[x][y] && !isMerged[nx][y]) {
                    map[nx][y] *= 2;
                    map[x][y] = 0;
                    isMerged[nx][y] = true;
                }
            }
        }
    }

    private void goDown() {
        for (int y = 0; y < N; y++) {
            for (int x = N - 2; x >= 0; x--) {
                for (int nx = x + 1; nx < N && map[nx][y] == 0; nx++) {
                    map[nx][y] = map[nx - 1][y];
                    map[nx - 1][y] = 0;
                }
                if (nx < N && map[nx][y] == map[x][y] && !isMerged[nx][y]) {
                    map[nx][y] *= 2;
                    map[x][y] = 0;
                    isMerged[nx][y] = true;
                }
            }
        }
    }
}

시간 복잡도 분석

이 코드의 시간 복잡도는 각 방향으로 타일을 이동시킬 때 𝑁^2의 타일을 최대 𝑁번까지 이동시킬 수 있으므로, 최악의 경우 𝑂(𝑁^3)의 시간 복잡도를 가진다. 하지만 일반적인 경우에는 타일이 공백 없이 밀착되어 있지 않기 때문에, 실제로는 𝑂(𝑁^2)에 가깝게 동작할 것이다.

느낀점

2048 게임의 기본 원리를 알고리즘으로 구현하는 것은 매우 흥미로운 문제이다. 이 문제를 통해 2차원 배열을 사용한 시뮬레이션 문제를 해결하는 기법을 다시 한 번 연습할 수 있었다. 또한, 문제를 세심하게 이해하고 요구사항에 맞게 정확히 구현하는 능력을 키울 수 있었다.