[C++] 백준 12100번 2048 (Easy)

12100번: 2048 (Easy)

삼성 SW 역량 테스트 기출 문제 수록 문제.

상, 하, 좌, 우를 잘 움직일 수 있다면 풀 수 있는 문제.

 

문제 조건

문제 조건은 생각보다 간단하다.

• 보드의 모든 블럭들을 상, 하, 좌, 우로 이동. (보드를 눕히는 형태로 이동.)
  
  
• 이 때, 같은 숫자의 블럭은 합쳐지는데, 한 번의 이동마다 한 번만 합쳐진다.

보드 크기 n * n에서, 최대 5번 이동 후 만들 수 있는 가장 큰 블록의 값을 찾으면 된다.

 

보드 움직이는 조건

상, 우, 하, 좌로 블럭을 하나씩 움직이면 된다.

(r, c)를 좌표로 나타낼 때

• 상 : r이 작은 것부터, c는 1 ~ n
• 우 : c가 큰 것부터, r은 1 ~ n
• 하 : r이 큰 것부터, c는 1 ~ n
• 좌 : c가 작은 것부터, r은 1 ~ n

또한 움직일 좌표에서 합쳐졌는 지 여부도 저장을 해야한다.

 

나같은 경우는 큐를 이용해서 구현하려 했다.

큐에는 다음과 같은 정보를 저장했다.

• 현재 보드의 정보
• 몇 번째 움직인 것인지 (idx)

 

코드 전문

/*
* 백준 12100번 2048 (Easy)
* https://www.acmicpc.net/problem/12100
* 구현 / 시뮬레이션
*/

#include <iostream>
#include <queue>

using namespace std;

struct BoardInfo {
	int board[21][21];
	int idx;
};

struct Point {
	int r;
	int c;
};

int widthHeight;
bool already[21][21];
int result;
queue<BoardInfo> q;

void go() {

	while (!q.empty()) {
		BoardInfo currentBoard = q.front();
		q.pop();
		if (currentBoard.idx > 5) { return; }

		//cout << "idx : " << currentBoard.idx << "\n";
		// 최대값 찾기.
		for (int j = 1; j <= widthHeight; j++) {
			for (int k = 1; k <= widthHeight; k++) {
				//cout << currentBoard.board[j][k] << " ";
				if (result < currentBoard.board[j][k]) {
					result = currentBoard.board[j][k];
				}
			}
			//cout << "\n";
		}
		//cout << "\n\n";
		//cout << currentBoard.idx << " , " << result << "\n";

		// 1. 위로 이동
		BoardInfo nextBoard;
		nextBoard.idx = currentBoard.idx + 1;
		for (int j = 1; j <= widthHeight; j++) {
			for (int k = 1; k <= widthHeight; k++) {
				nextBoard.board[j][k] = currentBoard.board[j][k];
				already[j][k] = false;
			}
		}

		for (int c = 1; c <= widthHeight; c++) {
			for (int r = 1; r <= widthHeight; r++) {
				int curR = r;
				int nxtR = r - 1;
				if (nextBoard.board[curR][c] == 0) { continue; }
				while (nxtR >= 1) {
					if (nextBoard.board[nxtR][c] == 0) {
						nextBoard.board[nxtR][c] = nextBoard.board[curR][c];
						nextBoard.board[curR][c] = 0;
						curR -= 1;
						nxtR -= 1;
					}
					else if (nextBoard.board[curR][c] == nextBoard.board[nxtR][c] && !already[nxtR][c]) {
						already[nxtR][c] = true;
						nextBoard.board[curR][c] = 0;
						nextBoard.board[nxtR][c] *= 2;
						break;
					}
					else {
						break;
					}
				}
			}
		}
		q.push(nextBoard);

		// 2. 우로 이동
		BoardInfo nextBoard2;
		nextBoard2.idx = currentBoard.idx + 1;
		for (int j = 1; j <= widthHeight; j++) {
			for (int k = 1; k <= widthHeight; k++) {
				nextBoard2.board[j][k] = currentBoard.board[j][k];
				already[j][k] = false;
			}
		}

		for (int r = 1; r <= widthHeight; r++) {
			for (int c = widthHeight; c >= 1; c--) {
				int curC = c;
				int nxtC = c + 1;
				if (nextBoard2.board[r][curC] == 0) { continue; }

				while (nxtC <= widthHeight) {
					if (nextBoard2.board[r][nxtC] == 0) {
						nextBoard2.board[r][nxtC] = nextBoard2.board[r][curC];
						nextBoard2.board[r][curC] = 0;
						curC += 1;
						nxtC += 1;
					}
					else if (nextBoard2.board[r][curC] == nextBoard2.board[r][nxtC] && !already[r][nxtC]) {
						already[r][nxtC] = true;
						nextBoard2.board[r][curC] = 0;
						nextBoard2.board[r][nxtC] *= 2;
						break;
					}
					else {
						break;
					}
				}
			}
		}
		q.push(nextBoard2);

		// 3. 아래로 이동
		BoardInfo nextBoard3;
		nextBoard3.idx = currentBoard.idx + 1;
		for (int j = 1; j <= widthHeight; j++) {
			for (int k = 1; k <= widthHeight; k++) {
				nextBoard3.board[j][k] = currentBoard.board[j][k];
				already[j][k] = false;
			}
		}

		for (int c = 1; c <= widthHeight; c++) {
			for (int r = widthHeight; r >= 1; r--) {
				int curR = r;
				int nxtR = r + 1;
				if (nextBoard3.board[curR][c] == 0) { continue; }
				while (nxtR <= widthHeight) {
					if (nextBoard3.board[nxtR][c] == 0) {
						nextBoard3.board[nxtR][c] = nextBoard3.board[curR][c];
						nextBoard3.board[curR][c] = 0;
						curR += 1;
						nxtR += 1;
					}
					else if (nextBoard3.board[curR][c] == nextBoard3.board[nxtR][c] && !already[nxtR][c]) {
						already[nxtR][c] = true;
						nextBoard3.board[curR][c] = 0;
						nextBoard3.board[nxtR][c] *= 2;
						break;
					}
					else {
						break;
					}
				}
			}
		}
		q.push(nextBoard3);

		// 4. 좌로 이동
		BoardInfo nextBoard4;
		nextBoard4.idx = currentBoard.idx + 1;
		for (int j = 1; j <= widthHeight; j++) {
			for (int k = 1; k <= widthHeight; k++) {
				nextBoard4.board[j][k] = currentBoard.board[j][k];
				already[j][k] = false;
			}
		}

		for (int r = 1; r <= widthHeight; r++) {
			for (int c = 1; c <= widthHeight; c++) {
				int curC = c;
				int nxtC = c - 1;
				if (nextBoard4.board[r][curC] == 0) { continue; }

				while (nxtC >= 1) {
					if (nextBoard4.board[r][nxtC] == 0) {
						nextBoard4.board[r][nxtC] = nextBoard4.board[r][curC];
						nextBoard4.board[r][curC] = 0;
						curC -= 1;
						nxtC -= 1;
					}
					else if (nextBoard4.board[r][curC] == nextBoard4.board[r][nxtC] && !already[r][nxtC]) {
						already[r][nxtC] = true;
						nextBoard4.board[r][curC] = 0;
						nextBoard4.board[r][nxtC] *= 2;
					}
					else {
						break;
					}
				}
			}
		}
		q.push(nextBoard4);
	}
}

int main() {
	cin >> widthHeight;

	BoardInfo firstBoard;
	firstBoard.idx = 0;

	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			cin >> firstBoard.board[i][j];
		}
	}

	q.push(firstBoard);

	go();

	cout << result;
}

어떻게 짤까 하다가, 그냥 노가다 하는 형식으로 짰다.

입력을 받은 후, 큐에 넣으면서 index가 5를 넘지 않는 선에서 구현하도록 만들었다.

상, 하, 좌, 우 4번을 5번 움직이고

한 보드의 크기가 최대 400번이므로 1,024 * 400 = 400,024로 시간 제한에 걸리지 않을 거라고 판단했다.

 

코드는 중복된 코드가 많기도 하지만, 그냥 블록을 하나씩 움직이는 거라고 생각하면 된다.

 

많이 틀리게 돼서, 반례들을 찾아도 다 올바른 정답이 나와서 대체 뭐가 문제인 지 한참을 찾아야 했다.

 

그러다 struct 안에 idx가 0이 아닌, 다른 수로 초기화 되는 것을 발견했고

idx를 1로 초기화하니까 맞을 수 있었다.

초기화 실수하지 말자.