문제 링크

성능 요약

메모리: 31780 KB, 시간: 212 ms

분류

백트래킹, 브루트포스 알고리즘, 구현, 시뮬레이션

제출 일자

2025년 2월 18일 18:54:06

문제 설명

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

풀이

느낀점

• 구현은 역시 원본, 복제복의 초기화 타이밍이 가장 중요한 것 같다.
• 초기화 위치 잘못 설정해서 디버깅이 또 오래걸렸다..

설계 : 15분

• 판 상태를 이동할 수 있는 네 방향에 따라 dfs 로 경우의 수를 확인한다.
• 이동해도 판에 변화가 없는 경우는 더이상 확인하지 않는다.
• 특정 상태에 대한 다음 경우의 수는 판 상태를 복제하여 재귀함수로 적용한다.
• 게임규칙에 대한 구현은 각 이동 방향의 반대 방향으로 숫자를 순회하여 연속으로 같은수가 나오면 더하여 갱신하는 방식으로 했다.
  
• 상세한 내용은 주석 참고

코드(Java)

• 구현 시간: 160분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 2048 (Easy)_12100
 * Date: 2025.02.18
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static boolean[] dr = {false, false, true, false};	// 행 역순이어야 하냐
	static boolean[] dc = {false, true, false, false};	// 열 역순이어야 하냐
	static boolean[] rFir = {false, true, false, true};	// 행 우선순회냐
	static int n;
	static int answer;
	static Deque<Integer> deque;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// n, 보드, answer 초기화
		n = Integer.parseInt(br.readLine());
		int[][] board = new int[n][n];
		answer = 0;

		// board 초기 상태 입력 및 최대값 저장
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				answer = Math.max(answer, board[i][j]);
			}
		}

		// 시뮬레이션
		dfs(0, board);

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}

	public static void dfs(int cnt, int[][] board) {

		// 5회까지 이동해봤으면 리턴
		if (cnt >= 5) return;

		// 4가지 방향 확인
		for (int d = 0; d < 4; d++) {

			// 다음 경우의 수로 넘길 보드 판 복제본
			int[][] copy = new int[n][];
			for (int i = 0; i < n; i++) copy[i] = Arrays.copyOf(board[i], n);

			// 보드판에 변경사항이 있는지 체크
			boolean changed = false;

			// 이동 방향에 따라 순회하며 열 또는 행 마다 숫자 갱신
			for (int i = 0; i < n; i++) {
				deque = new ArrayDeque<>();
				for (int j = 0; j < n; j++) {
					// 행 우선순회 방향이면 가로로 하나의 행을 순서대로 큐에 저장(0 제외)
					if (rFir[d] && copy[i][j] != 0) deque.addLast(copy[i][j]);
					// 열 우선순회 방향이면 세로로 하나의 열을 순서대로 큐에 저장(0 제외)
					else if (!rFir[d] && copy[j][i] != 0) deque.addLast(copy[j][i]);
				}

				// 역순회 여부에 따라 갱신된 열/행 반환
				int[] newLine = rFir[d] ? getNew(dc[d]) : getNew(dr[d]);

				// 변화가 있을 때만 copy 배열에 갱신 (하나라도 갱신되면 changed = true)
				for (int j = 0; j < n; j++) {
					// 행 우선 순회라면 가로방향으로 갱신
					if (rFir[d] && copy[i][j] != newLine[j]) {
						copy[i][j] = newLine[j];
						changed = true;
					}
					// 열 우선 순회라면 세로방향으로 갱신
					else if (!rFir[d] && copy[j][i] != newLine[j]) {
						copy[j][i] = newLine[j];
						changed = true;
					}
				}
			}

			// 하나라도 달라진 자리가 있다면 다음 경우의 수 탐색
			if (changed) dfs(cnt + 1, copy);
		}
	}

	public static int[] getNew(boolean deOrder) {
		int[] line = new int[n];
		int idx = deOrder ? n-1 : 0;	// 순회 방향에 따라 line 배열을 채울 idx 시작점 설정
		int move = deOrder ? -1 : 1;	// 순회 방향에 따라 line 배열을 채워갈 idx 변화값 설정

		int before = 0;

		// deque에서 0이 나올 일은 없음.
		while (!deque.isEmpty()) {
			int curr = poll(deOrder);	// 순회 방향에 따라 큐에서 꺼내는 방향 설정

			// 새로 꺼낸 수가 이전의 수와 같으면
			if (before == curr) {
				line[idx] = curr + curr;		// 두배 값을 line[idx]에 추가
				answer = Math.max(answer, line[idx]);	// 최대값 갱신
				before = 0;						// 먼저 합쳐진 수는 다시 합쳐질 수 없으므로 before = 0 으로 초기화
				idx += move;					// idx 갱신

			// 새로 꺼낸 수와 이전의 수가 다르면
			} else {
				// 이전의 수가 0이 아니라면
				if (before != 0) {
					line[idx] = before;		// line[idx]에 이전 값 추가
					idx += move;			// idx 갱신
				}
				before = curr;			// 이전 값을 새로 꺼낸 수로 갱신
			}
		}
		if (before != 0) line[idx] = before;	// 마지막 before 상태가 0이 아니라면(즉, 값이 있다면) line[idx]에 추가

		return line;
	}

	public static int poll(boolean deOrder) {
		if (deOrder) return deque.pollLast();
		return deque.pollFirst();
	}
}