[백준] 12100번 - 2048(Easy)

 

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

https://play2048.co/

2048

✏️원리 

예전에 2048게임을 많이 했었는데, 이렇게 알고리즘 문제로 풀게되니 신기했다.

 

우선 2048은 동서남북, 이렇게 4방향으로 블록을 움직일 수 있고, 서로 인접한 블록의 수가 같은면 합칠 수 있는 원리이다.

 

자세히 보면 한가지 방향으로 움직일때, 우선 그 방향으로 블록들을 다 밀어줘야 한다는 것을 깨달았다.

 

그래서 방향에 기준해서 0인 값들이 중간 중간에 있지 않도록, 한 방향으로 수를 몰아 넣어 줄 수 있는 flush 메소드를 만들었다.

 

flush 메소드는 움직이는 방향에 관련 한 줄만 뽑아 그 방향으로만 밀어주는 원리이다.

 

 

아래 배열을 서(left) 방향으로 flush 해준다 했을 때,

2

0

0

2

2

이렇게 된다.

2

2

2

0

0

 

flush 메소드

vector<int> flush(vector<int> fl) {
	vector<int> res;
	int cnt = 0;
	for (int i = 0; i < fl.size(); ++i) {
		if (fl[i] != 0) {
			res.push_back(fl[i]);
		}
		else {
			cnt++;
		}
	}

	while (cnt > 0) {
		res.push_back(0);
		cnt--;
	}

	return res;
}

 

이제 아래와 같이 한 방향으로 각 배열마다 flush 메소드를 이용하면서, 조건에 맞춰 만들어 주면 된다.

 

(예시)

 

서(left) 방향으로 블록을 옮겨주는 경우

 

북(up) 방향으로 블록을 옮겨주는 경우

✏️ 조건

 

1. 바로 뒤에 인접한 수가 나오는 경우

-> 두 수를 합친 수(*2)를 저장해주고, 그 인접한 수는 0으로 해주면 된다.

 

2. 0인 경우

-> flush를 해주고 0인 경우이므로 끝났음을 알 수 있다.

 

※ 주의 : 방향마다 인덱스가 다르므로 신중히 만들어 주자

 

📃 구현 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;

int maxNum = 0;



vector<int> flush(vector<int> fl) {
	vector<int> res;
	int cnt = 0;
	for (int i = 0; i < fl.size(); ++i) {
		if (fl[i] != 0) {
			res.push_back(fl[i]);
		}
		else {
			cnt++;
		}
	}

	while (cnt > 0) {
		res.push_back(0);
		cnt--;
	}

	return res;
}

vector<vector<int>> up(vector<vector<int>> arr) {

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N - 1; ++j) {
			

			vector<int> fl;
			for (int e = j; e < N; ++e) {
				fl.push_back(arr[e][i]);
			}
			fl = flush(fl);

			int f = 0;

			for (int e = j; e < N; ++e) {
				arr[e][i] = fl[f++];
			}


			if (arr[j][i] == 0) {
				break;
			}

			if (arr[j][i] == arr[j + 1][i]) {
				arr[j][i] *= 2;
				arr[j + 1][i] = 0;			
			}

		}		
	}
	return arr;


	
}


vector<vector<int>> down(vector<vector<int>> arr) {
	
	for (int i = 0; i < N; ++i) {
		for (int j = N-1; j > 0; --j) {
			


			vector<int> fl;
			for (int e = j; e >= 0; --e) {
				fl.push_back(arr[e][i]);
			}
			fl = flush(fl);

			int f = 0;

			for (int e = j; e >= 0; --e) {
				arr[e][i] = fl[f++];
			}



			if (arr[j][i] == 0) {
				break;
			}

			if (arr[j][i] == arr[j - 1][i]) {
				arr[j][i] *= 2;
				arr[j-1][i] = 0;
			}
		}
	}

	return arr;

}

vector<vector<int>> left(vector<vector<int>> arr) {


	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N - 1; ++j) {
			

			vector<int> fl;
			for (int e = j; e < N; ++e) {
				fl.push_back(arr[i][e]);
			}
			fl = flush(fl);

			int f = 0;

			for (int e = j; e < N; ++e) {
				arr[i][e] = fl[f++];
			}


			if (arr[i][j] == 0) {
				break;
			}
			
			if (arr[i][j] == arr[i][j+1]) {
				arr[i][j] *= 2;
				arr[i][j+1] = 0;
			}
		}
		
	}

	return arr;
}

vector<vector<int>> right(vector<vector<int>> arr) {
	

	for (int i = 0; i < N; ++i) {
		for (int j = N - 1; j > 0; --j) {
			

			vector<int> fl;
			for (int e = j; e >= 0; --e) {
				fl.push_back(arr[i][e]);
			}
			fl = flush(fl);

			int f = 0;

			for (int e = j; e >= 0; --e) {
				arr[i][e] = fl[f++];
			}


			if (arr[i][j] == 0) {
				break;
			}

			if (arr[i][j] == arr[i][j-1]) {
				arr[i][j] *= 2;
				arr[i][j-1] = 0;
			}
			
		}

	}

	return arr;

	
}

void searchMax(vector<vector<int>> arr) {


	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (arr[i][j] > maxNum) {
				maxNum = arr[i][j];
			}
		}

	}

}


void game(vector<vector<int>> arr, int count, int mode) {
	if (count > 5) {
		searchMax(arr);
		return;
	}

	if (mode == 0) {
		arr = up(arr);
	}
	else if(mode ==1) {
		arr = down(arr);
	}
	else if (mode == 2) {
		arr = left(arr);
	}
	else if (mode == 3) {
		arr = right(arr);
	}

	game(arr, count + 1, 0);
	game(arr, count + 1, 1);
	game(arr, count + 1, 2);
	game(arr, count + 1, 3);

}


int main() {
	cin >> N;
	
	vector<vector<int>> arr;
	arr = vector<vector<int>>(N, vector<int>(N, 0));

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			int tmp;
			cin >> tmp;
			arr[i][j] = tmp;
		}
	}


	game(arr, 1, 0);
	game(arr, 1, 1);
	game(arr, 1, 2);
	game(arr, 1, 3);


	cout << maxNum;

}

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!