문제

BOJ 12100, 2048(Easy)

핵심

• 입력의 크기가 작아 구현에 초점을 맞춘다.
• 2048 게임과 규칙이 똑같다. 한 방향으로 밀어 같은 숫자라면 합쳐지게 된다. 같은 숫자가 아니고, 해당 방향에 숫자가 없다면 앞에서 부터 채워진다. 최대 한 번만 합쳐진다. 자세한 동작 방식은 아래 링크에 있다.
  2048 게임
• 상, 하, 좌, 우 최대 5번 밀어 정사각형에서 최댓값을 찾는 문제이다. 구현할 때 실수를 덜기 위해서 아래에서 위로 미는 방향(0으로 미는 방향) 하나를 구현하고, 정사각형을 회전시켜 다른 방향으로 회전하는 것을 대체할 수 있다. 0으로 미는 방향을 구현하면, 90도 회전해서 3으로 미는 방향, 2로 미는 방향, 1로 미는 방향을 구현할 수 있다. 아래 그림을 참고하자.
  
• 해당 문제는 크게 세 부분으로 나눌 수 있다. 첫째로는 상, 하, 좌, 우로 5번을 밀 때 생길 수 있는 경우의 수다. $4^5$이므로 1024가 나오는데 이는 dfs 또는 진법 변환 방식으로 구할 수 있다.

void dfs(int depth, vector<int>& seq) {
	if (depth == 5) {
		for (int i = 0; i < (int)seq.size(); ++i) {
			cout << seq[i] << ' ';
		}
		cout << '\n';
		return ;
	}
	for (int i = 0; i < 4; ++i) {
		seq.push_back(i);
		dfs(depth + 1, seq);
		seq.pop_back();
	}
}

• 진법 변환 방식은 아래와 같다.

for (int i = 0; i < (1 << (2 * 5)); ++i) {
	int seq = i;
	for (int i = 0; i < 5; ++i) {
		cout << seq % 4 << ' ';
		seq /= 4;
	}
	cout << '\n';
}

• 두 번째로는 정사각형을 아래에서 위로 밀어주는 부분이다. 0이라면 건너뛰고 0이 아니라면 임시 배열에 채워 넣는다. tmp배열과 숫자가 다르다면 다음 칸에 채워주고 같다면 이를 합쳐주었다. 코드로 나타내면 아래와 같다.

for (int row = 0; row < n; ++row) {
	if (cBoard[row] == 0)
		continue;
	if (tmp[idx] == 0)
		tmp[idx] = cBoard[row];
	else if (tmp[idx] != cBoard[row])
		tmp[++idx] = cBoard[row];
	else (tmp[idx] == cBoard[row])
		tmp[idx++] *= 2;
}

• 세 번째로는 회전하는 부분으로 행이 열로 가는 성질을 이용해 다음 수식을 이용하였다.

for (int i = 0; i < n; ++i) {
	for (int j = 0; j < n; ++j)
		tmp[j][n - i - 1] = board[i][j];
}

• 이 세 부분을 이해했다면, 코드를 읽는 데 어려움이 없을 것이다.

개선

코드

시간복잡도

• $O(4^5\times n^2)$

C++

#include <iostream>
#include <vector>
using namespace std;

int n;
int board[24][24];
int cBoard[24][24];
int ans = 0;
void push() {
	for (int col = 0; col < n; ++col) {
		int tmp[24] = {};
		int idx = 0;
		for (int row = 0; row < n; ++row) {
			if (cBoard[row][col] == 0)
				continue;
			if (tmp[idx] == 0)
				tmp[idx] = cBoard[row][col];
			else if (tmp[idx] != cBoard[row][col])
				tmp[++idx] = cBoard[row][col];
			else if (tmp[idx] == cBoard[row][col])
				tmp[idx++] *= 2;
		}
		for (int i = 0; i < n; ++i)
			cBoard[i][col] = tmp[i];
	}
}

void rotate(int cnt) {
	if (cnt == 0 || cnt == 4)
		return ;
	while (cnt--) {
		int tmp[24][24] = {};
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j)
				tmp[j][n - i - 1] = cBoard[i][j];
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j)
				cBoard[i][j] = tmp[i][j];
		}
	}
}

void dfs(int depth, vector<int>& seq) {
	if (depth == 5) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j)
				cBoard[i][j] = board[i][j];
		}
		int restoreCnt = 0;
		for (int i = 0; i < (int)seq.size(); ++i) {
			rotate(seq[i]);
			push();
			restoreCnt = 4 - seq[i];
			rotate(restoreCnt);
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j)
				ans = max(ans, cBoard[i][j]);
		}
		return ;
	}
	for (int i = 0; i < 4; ++i) {
		seq.push_back(i);
		dfs(depth + 1, seq);
		seq.pop_back();
	}
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			cin >> board[i][j];
	}
	vector<int> seq;
	dfs(0, seq);
	cout << ans;
}

Java

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

public class Main {
    static int n;
    static int[][] board = new int[24][24];
    static int[][] cBoard = new int[24][24];
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++)
                board[i][j] = Integer.parseInt(st.nextToken());
        }
        dfs(0, new ArrayList<>());
        System.out.println(ans);
    }

    static void dfs(int depth, ArrayList<Integer> seq) {
        if (depth == 5) {
            for (int i = 0; i < n; i++)
                System.arraycopy(board[i], 0, cBoard[i], 0, n);
            int restoreCnt = 4;
            for (int rotation : seq) {
                rotate(rotation);
                push();
                restoreCnt -= rotation;
                rotate(restoreCnt);
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    ans = Math.max(ans, cBoard[i][j]);
            }
            return;
        }
        for (int i = 0; i < 4; i++) {
            seq.add(i);
            dfs(depth + 1, seq);
            seq.remove(seq.size() - 1);
        }
    }

    static void rotate(int cnt) {
        if (cnt == 0 || cnt == 4)
            return;
        while (cnt-- > 0) {
            int[][] tmp = new int[24][24];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    tmp[j][n - i - 1] = cBoard[i][j];
            }
            for (int i = 0; i < n; i++)
                System.arraycopy(tmp[i], 0, cBoard[i], 0, n);
        }
    }

    static void push() {
        for (int col = 0; col < n; col++) {
            int[] tmp = new int[24];
            int idx = 0;
            for (int row = 0; row < n; row++) {
                if (cBoard[row][col] == 0) continue;
                if (tmp[idx] == 0) tmp[idx] = cBoard[row][col];
                else if (tmp[idx] != cBoard[row][col]) tmp[++idx] = cBoard[row][col];
                else tmp[idx++] *= 2;
            }
            for (int i = 0; i < n; i++) cBoard[i][col] = tmp[i];
        }
    }
}