Written by Daeyeol Sung
[ Algorithm ] 백준 2048(Easy) (12100번)
오늘 풀이 할 문제는 백준 2048(Easy) 문제이다. 이 문제 또한 삼성 SW 역량 테스트 기출 문제 문제집에 있는 문제이다. 다들 한 번쯤은 해본 2048 게임의 알고리즘 문제인데 어려운 로직은 없지만 반복되는 코드가 많아서 코드가 길어지다보니 자잘한 오류를 잡지 못해서 푸는데 오래 걸렸다. 그래서 2번 풀고 조금 더 정돈된 풀이를 올린다.
문제
문제는 여기에 참조한다. 문제를 풀 때 고려해야 할 조건을 적어봤다.
- 전체 블록을 상하좌우로 움직일 수 있으며,
- 움직여서 같은 숫자의 블록이 2개 만나면 배수로 합쳐지게 된다.
- 최대 5번 움직여서 가장 큰 블록의 값을 만든다.
- 한 번 합쳐진 블록은 다시 합쳐질 수 없다.
풀이
움직일 수 있는 경우가 4가지 이므로 if문을 써서 4가지 경우로 나눴다.
결국 라인 단위로 나눠서 합치는 기능을 구현해야 하기 때문에 위, 아래로 이동시키는 경우는 열을 고정시키고 행을 따라 탐색해야 하고 왼쪽, 오른쪽으로 이동시키는 경우는 행을 고정하고 열을 따라 탐색해야 한다. 위, 아래로 이동시키는 경우만 알면 왼쪽, 오른쪽으로 이동시키는 경우도 바로 이해 할 수 있을 것이다.
private static void move(int[][] board, int dir) {
// 위로 이동시키는 경우
if(dir == 0) {
for(int i = 0; i < n; i++) {
List<Integer> line = new ArrayList<>();
// 각 라인에서 0이 아닌 숫자를 리스트에 저장
for(int j = 0; j < n; j++) {
if(board[j][i] != 0) line.add(board[j][i]);
}
// 각 라인을 이동시켜서 합치기
List<Integer> mergedLine = merge(line);
// 합친 결과를 다시 원래 라인에 저장
for(int j = 0; j < n; j++) {
if(j < mergedLine.size()) {
board[j][i] = mergedLine.get(j);
}
else board[j][i] = 0;
}
}
}
// 아래로 이동시키는 경우
else if(dir == 1) {
// 각 라인에서 0이 아닌 숫자를 리스트에 저장
for(int i = 0; i < n; i++) {
List<Integer> line = new ArrayList<>();
for(int j = n-1; j >= 0; j--) {
if(board[j][i] != 0) line.add(board[j][i]);
}
// 각 라인을 이동시켜서 합치기
List<Integer> mergedLine = merge(line);
// 합친 결과를 다시 원래 라인에 저장
int idx = 0;
for(int j = n-1; j >= 0; j--) {
if(idx < mergedLine.size()) {
board[j][i] = mergedLine.get(idx);
idx++;
}
else board[j][i] = 0;
}
}
}
.
.
.
우선 각 라인에서 0이 아닌 숫자들을 저장할 리스트 line을 만들고 각 라인을 따라 탐색하며 0이 아닌 숫자들만 저장한다. 리스트에 저장이 끝나면 이제 그 숫자들에 대해 합치기를 진행해야 하는데 합치기는 모든 경우에서 중복되기 때문에 따로 메소드로 뺐다.
private static List<Integer> merge(List<Integer> line) {
List<Integer> mergedLine = new ArrayList<>();
// 앞에서부터 같은 숫자가 있는 경우 합쳐서 리스트에 추가
int i = 0;
while(i < line.size()) {
if(i+1 < line.size() && line.get(i).equals(line.get(i+1))) {
mergedLine.add(line.get(i)*2);
i+=2;
}
else {
mergedLine.add(line.get(i));
i++;
}
}
return mergedLine;
}
line 리스트를 탐색하며 연속되게 같은 경우가 있는 경우는 그 배수를 mergedLine 리스트에 저장한다. 즉, 같은 숫자 2개가 연속되면 그 배수를 저장하고 아니라면 원래 숫자를 저장한다.
참고로 숫자 2개를 비교할 때 리스트에 들어있는 것은 기본 자료형 int가 아닌 객체형 Integer이므로 equals() 메소드를 사용해야 안전하게 비교할 수 있다.
다음으로 반환 받은 mergedLine 리스트의 숫자들을 다시 원래 라인에 저장하면 된다. 주의 해야 할 점은 아래로 이동시키는 경우는 mergedLine 리스트의 숫자들을 다시 원래 라인에 저장할 때 원래 라인의 뒤에서부터 저장해야 한다. 처음 0이 아닌 숫자들을 line 리스트에 저장할 때부터 역순으로 저장했기 때문이다.
이제 보드를 모든 방향으로 이동하고 합치는 기능까지 구현 했으니 DFS를 사용해서 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 계산하면 된다.
private static void dfs(int depth, int[][] board) {
// 5번 이동하고 나면 가장 큰 블록 갱신
if(depth == 5) {
int max = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
max = Math.max(max, board[i][j]);
}
}
bigBlock = Math.max(bigBlock, max);
return;
}
for(int i = 0; i < 4; i++) {
int[][] copyBoard = copy(board);
move(copyBoard, i);
dfs(depth+1, copyBoard);
}
}
현재 상태에 대한 복사본 보드를 만들고 상하좌우 중 한 방향으로 이동시키고 재귀하면 된다. 주의 할 점이 2가지 있다.
- 복사본을 만들어서 재귀하지 않으면 모든 호출이 같은 보드의 상태를 공유하게 되므로 제대로된 결과를 얻을 수 없다. 원본 보드는 수정하지 않고 복사본 보드를 사용해 이동과 재귀를 했기 때문에 재귀 호출 5번을 끝내고 나오면 백트래킹 또한 자연스럽게 된다.
- 복사본을 재귀 하기 전에 한 번만 만들어야지 move() 메소드 안에서 매번 복사하고 수정한 복사본을 반환하는 식으로 코드를 작성하면 메모리 초과가 날 수 있다.
마지막으로 전체 코드이다.
import java.io.*;
import java.util.*;
public class Main {
static int n, bigBlock;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
bigBlock = 0;
int[][] board = new int[n][n];
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, board);
System.out.println(bigBlock);
}
private static void dfs(int depth, int[][] board) {
// 5번 이동하고 나면 가장 큰 블록 갱신
if(depth == 5) {
int max = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
max = Math.max(max, board[i][j]);
}
}
bigBlock = Math.max(bigBlock, max);
return;
}
for(int i = 0; i < 4; i++) {
int[][] copyBoard = copy(board);
move(copyBoard, i);
dfs(depth+1, copyBoard);
}
}
private static void move(int[][] board, int dir) {
// 위로 이동시키는 경우
if(dir == 0) {
for(int i = 0; i < n; i++) {
List<Integer> line = new ArrayList<>();
// 각 라인에서 0이 아닌 숫자를 리스트에 저장
for(int j = 0; j < n; j++) {
if(board[j][i] != 0) line.add(board[j][i]);
}
// 각 라인을 이동시켜서 합치기
List<Integer> mergedLine = merge(line);
// 합친 결과를 다시 원래 라인에 저장
for(int j = 0; j < n; j++) {
if(j < mergedLine.size()) {
board[j][i] = mergedLine.get(j);
}
else board[j][i] = 0;
}
}
}
// 아래로 이동시키는 경우
else if(dir == 1) {
// 각 라인에서 0이 아닌 숫자를 리스트에 저장
for(int i = 0; i < n; i++) {
List<Integer> line = new ArrayList<>();
for(int j = n-1; j >= 0; j--) {
if(board[j][i] != 0) line.add(board[j][i]);
}
// 각 라인을 이동시켜서 합치기
List<Integer> mergedLine = merge(line);
// 합친 결과를 다시 원래 라인에 저장
int idx = 0;
for(int j = n-1; j >= 0; j--) {
if(idx < mergedLine.size()) {
board[j][i] = mergedLine.get(idx);
idx++;
}
else board[j][i] = 0;
}
}
}
// 왼쪽으로 이동시키는 경우
else if(dir == 2) {
for(int i = 0; i < n; i++) {
List<Integer> line = new ArrayList<>();
// 각 라인에서 0이 아닌 숫자를 리스트에 저장
for(int j = 0; j < n; j++) {
if(board[i][j] != 0) line.add(board[i][j]);
}
// 각 라인을 이동시켜서 합치기
List<Integer> mergedLine = merge(line);
// 합친 결과를 다시 원래 라인에 저장
for(int j = 0; j < n; j++) {
if(j < mergedLine.size()) {
board[i][j] = mergedLine.get(j);
}
else board[i][j] = 0;
}
}
}
// 오른쪽으로 이동시키는 경우
else {
for(int i = 0; i < n; i++) {
List<Integer> line = new ArrayList<>();
// 각 라인에서 0이 아닌 숫자를 리스트에 저장
for(int j = n-1; j >= 0; j--) {
if(board[i][j] != 0) line.add(board[i][j]);
}
// 각 라인을 이동시켜서 합치기
List<Integer> mergedLine = merge(line);
// 합친 결과를 다시 원래 라인에 저장
int idx = 0;
for(int j = n-1; j >= 0; j--) {
if(idx < mergedLine.size()) {
board[i][j] = mergedLine.get(idx);
idx++;
}
else board[i][j] = 0;
}
}
}
}
private static List<Integer> merge(List<Integer> line) {
List<Integer> mergedLine = new ArrayList<>();
// 앞에서부터 같은 숫자가 있는 경우 합쳐서 리스트에 추가
int i = 0;
while(i < line.size()) {
if(i+1 < line.size() && line.get(i).equals(line.get(i+1))) {
mergedLine.add(line.get(i)*2);
i+=2;
}
else {
mergedLine.add(line.get(i));
i++;
}
}
return mergedLine;
}
private static int[][] copy(int[][] board) {
int[][] copyBoard = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
copyBoard[i][j] = board[i][j];
}
}
return copyBoard;
}
}