백준 12100 - 2048(Easy) (C++, 복습)

문제 링크입니다. https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

삼성 SW 역량테스트 문제였습니다.

 

2048 게임을 응용한 문제로, 상하좌우를 움직이는 것은 똑같지만 게임처럼 움직일 때마다 2가 생기지는 않습니다.

이때 나올 수 있는 최대 값을 구하는 문제였습니다.

출력 예시

먼저, 값이 더이상 변하지 않는 횟수가 몇 번인지를 찾아야합니다.

1줄에 최대 20개의 수가 주어질 수 있으니 한번 가정을 해보겠습니다.

Case 1, 2를 보면 각각 3번, 4번을 이동했을 때, 더 이상 값이 변하지 않음을 알 수 있습니다.

Case 2의 마지막에서 2개의 값이 같다면, 최대 5번까지 움직여야함으로 최대 5번을 움직이면 되겠습니다.

 

DFS 방식을 통해서 될 수 있는 경우를 모두 확인한 다음, 최댓값을 비교해 출력해주면 되겠습니다.

한 단계 DFS 탐색을 들어갈 때마다, 현재 map을 저장한 다음, DFS 탐색이 끝난 뒤, 저장한 현재 map을 덮으면 됩니다.

 

문제 접근 방법

1. 2048의 상하좌우 움직임을 구현한다.

2. DFS 1번 탐색을 시작한다.

3. 상하좌우 탐색을 각각 한 뒤, 다음 DFS 탐색을 시작한다.

4. 해당 과정을 연속하고 최댓값을 출력한다.

 

 

문제 접근 방법 - 1번 (up(), down(), left(), right() 함수를 참고해주세요)

상하좌우 움직임이 전부 비슷하니 up() 함수를 통해서 설명하겠습니다.

void up() {
	queue<int> q;
	for (int j = 1; j <= N; j++) {
		for (int i = 1; i <= N; i++) {
			if (map[i][j] != 0) {
				q.push(map[i][j]);
			}
			map[i][j] = 0;
		}
		int down = 1;
		while (!q.empty()) {
			int num = q.front();
			q.pop();
			if (map[down][j] == 0) {
				map[down][j] = num;
			}
			else if (map[down][j] == num) {
				map[down][j] *= 2;
				down++;
			}
			else {
				down++;
				map[down][j] = num;
			}
		}
	}
}

위로 움직일 경우, 열에 따라서 행이 움직입니다. 1열에 따라 1~N 행이 움직이거나, 2열을 기준으로 1~N열이 움직이는 형태입니다.

따라서 1열 일때, 1~N 행을 확인하여 값이 있는 경우 queue에 저장해줍니다. 그 뒤, 해당 행을 전부 0으로 바꿔줍니다.

queue가 전부 빌때까지, 위에서부터 값을 채워넣습니다. 

1. 해당 칸에 값이 0일 경우, 해당 queue의 값을 넣어줍니다.

2. 해당 칸의 값이 queue의 값과 같은 경우 -> 합쳐질 수 있음으로 *2를 해준 뒤, 한칸 내립니다. 

3. 해당 칸의 값이 queue의 값과 다른 경우 -> 합쳐질 수 없음으로 한칸 내려서 저장을 해줍니다.

해당 과정을 상하좌우에 따라 바꿔서 해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N;
int map[21][21];
int maxi;

void up() {
	queue<int> q;
	for (int j = 1; j <= N; j++) {
		for (int i = 1; i <= N; i++) {
			if (map[i][j] != 0) {
				q.push(map[i][j]);
			}
			map[i][j] = 0;
		}
		int down = 1;
		while (!q.empty()) {
			int num = q.front();
			q.pop();
			if (map[down][j] == 0) {
				map[down][j] = num;
			}
			else if (map[down][j] == num) {
				map[down][j] *= 2;
				down++;
			}
			else {
				down++;
				map[down][j] = num;
			}
		}
	}
}

void down() {
	queue<int> q;
	for (int j = 1; j <= N; j++) {
		for (int i = N; i >= 1; i--) {
			if (map[i][j] != 0) {
				q.push(map[i][j]);
			}
			map[i][j] = 0;
		}
		int down = N;
		while (!q.empty()) {
			int num = q.front();
			q.pop();
			if (map[down][j] == 0) {
				map[down][j] = num;
			}
			else if (map[down][j] == num) {
				map[down][j] *= 2;
				down--;
			}
			else {
				down--;
				map[down][j] = num;
			}
		}
	}
}

void left() {
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] != 0) {
				q.push(map[i][j]);
			}
			map[i][j] = 0;
		}
		int down = 1;
		while (!q.empty()) {
			int num = q.front();
			q.pop();
			if (map[i][down] == 0) {
				map[i][down] = num;
			}
			else if (map[i][down] == num) {
				map[i][down] *= 2;
				down++;
			}
			else {
				down++;
				map[i][down] = num;
			}
		}
	}
}

void right() {
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		for (int j = N; j >= 1; j--) {
			if (map[i][j] != 0) {
				q.push(map[i][j]);
			}
			map[i][j] = 0;
		}
		int down = N;
		while (!q.empty()) {
			int num = q.front();
			q.pop();
			if (map[i][down] == 0) {
				map[i][down] = num;
			}
			else if (map[i][down] == num) {
				map[i][down] *= 2;
				down--;
			}
			else {
				down--;
				map[i][down] = num;
			}
		}
	}
}

void match(int x) {
	if (x == 1) up();
	else if (x == 2) down();
	else if (x == 3) left();
	else right();
}

void find_maximum(int cnt) {
	if (cnt == 5) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				maxi = max(maxi, map[i][j]);
			}
		}
	}
	else {
		int copy_map[21][21];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				copy_map[i][j] = map[i][j];
			}
		}
		for (int i = 0; i < 4; i++) {
			match(i);
			find_maximum(cnt + 1);
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					map[i][j] = copy_map[i][j];
				}
			}
		}
	}
}

void solve() {
	find_maximum(0);
	cout << maxi;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!