백준 12100번 2048(easy) (삼성 SW 역량 테스트 기출 문제)

사용한 알고리즘 : 브루트포스 (완전탐색)

꽤나 구현이 어려운... 문제였습니다.
우선 i,j의 값을 pair<숫자, 합쳐진여부(0,1로 구분)>로 받았습니다.
각 움직임에서 값들이 한번 합쳐지면, 이후에는 합쳐지지 않으므로, 이를 표현하기 위해
합쳐졌다면 second 값을 1, 안합쳐 졌다면 0으로 구분해 주었습니다.

이후 이를 info라는 struct로 만들어, 이 안에서 count 값(움직인 횟수)을 세어 주었습니다.
움직인 횟수는 최대 5번입니다.
처음 생각은 각 움직임을 visited 라는 bool 함수로 체크하면서 가려고 했으나,
움직임의 순서마다 각 배열값이 달라진다는걸 깨달아 그냥 움직인 횟수만 체크했습니다.
예를들어 오른쪽 - 왼쪽 - 위 - 아래 움직임과,
왼쪽-오른쪽-아래-위 움직임은 그 배열들이 다를 수 있습니다.

움직임은 1: 오른쪽, 2: 왼쪽, 3: 위, 4: 아래  총 4방향입니다.
각 방향마다 움직일때 시작 점을 주의했어야 했습니다.
예를 들어 오른쪽으로 이동할 때는,
각 row는 끝값부터 봤어야 합니다.

각 움직임을 행해줄 함수 (GoDirect라는 이름) 를 만들었습니다.
단순한 구현이었고, 약간... 까다롭습니다.
이 함수를 돌릴때 배열이 변화가 있는지 체크하여 (Move라는 bool로)
변화가 있으면 count++ 해주고 변화된 info를 출력해주었습니다.

브루트포스는 dfs 식으로 구현했습니다.
각 dfs 에서 구하고자 하는 답 (ans라는 이름) 을 최신화 해 주었으며,
count가 5를 넘으면 return 했습니다.
각 4방향 (1:오른쪽,2:왼쪽,3:위,4:아래)를 먼저 만들어놓은 움직임을 행해주는 함수에 돌리고, 배열들에 변화가 있다면 이를 다시 dfs로 넣어주는 식으로 dfs를 구현했습니다.

참고로 저는 배열이 예를들어 ' 0 0 0 4 ' 일때 왼쪽으로 움직이는 과정에서
' 4 0 0 0 ' 이 되어야 하는데 ' 0 0 4 0 ' 식으로 한번밖에 움직여주지 않는 오류를 범해서 이를 찾는데 상당한 시간을 썼습니다.. ㅠ

제 구현실력이 좋지 못해 피치못하게 코드 길이가 길어진 점에 대해 죄송하게 생각합니다...
풀고보니 굉장히 지저분한 코드가 됐습니다...

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int>
	int N, ans;
	// dir = 0: 생략(visited 함수 쓰려고 비어놈),
	// 1: 오른쪽, 2: 왼쪽, 3: 위, 4: 아래;
	int dx[5] = {0,0,0,-1,1};
	int dy[5] = {0,1,-1,0,0};
	struct info{
	int cnt = 0;
	pii arr[21][21];
	};
	info GoDirect(info B, int dir){
	info temp = B;
	bool Move = false;
	// 오른쪽
	if(dir==1){
	for (int i = 0; i < N; ++i){
	for (int j = N-1; j >= 0; j--){
	int x = i;
	int y = j;
	if(temp.arr[x][y].first == 0) continue;
	if(temp.arr[x+dx[dir]][y+dy[dir]].first!=0 && temp.arr[x+dx[dir]][y+dy[dir]].first!=temp.arr[x][y].first) continue;
	if(temp.arr[x+dx[dir]][y+dy[dir]].second==1) continue;
	if(x+dx[dir]>=N || x+dx[dir]<0 || y+dy[dir]>=N || y+dy[dir]<0) continue;
	Move = true;
	int value = temp.arr[x][y].first;
	// 앞이 0 이면 전진
	while(x+dx[dir]<N && x+dx[dir]>=0 && y+dy[dir]<N && y+dy[dir]>=0){
	if(temp.arr[x+dx[dir]][y+dy[dir]].first==0){
	temp.arr[x][y] = pii(0,0);
	x+=dx[dir];
	y+=dy[dir];
	}
	else break;
	}
	// 앞이 같은 숫자면 합쳐
	if(temp.arr[x+dx[dir]][y+dy[dir]].first == value && temp.arr[x+dx[dir]][y+dy[dir]].second==0){
	temp.arr[x+dx[dir]][y+dy[dir]].first += value;
	temp.arr[x+dx[dir]][y+dy[dir]].second = 1;
	temp.arr[x][y] = pii(0,0);
	}
	// 못합치면 정지
	else temp.arr[x][y] = pii(value,0);
	}
	}
	}
	// 왼쪽
	else if(dir==2){
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	int x = i;
	int y = j;
	if(temp.arr[x][y].first == 0) continue;
	if(temp.arr[x+dx[dir]][y+dy[dir]].first!=0 && temp.arr[x+dx[dir]][y+dy[dir]].first!=temp.arr[x][y].first) continue;
	if(temp.arr[x+dx[dir]][y+dy[dir]].second==1) continue;
	if(x+dx[dir]>=N || x+dx[dir]<0 || y+dy[dir]>=N || y+dy[dir]<0) continue;
	Move = true;
	int value = temp.arr[x][y].first;
	// 앞이 0 이면 전진
	while(x+dx[dir]<N && x+dx[dir]>=0 && y+dy[dir]<N && y+dy[dir]>=0){
	if(temp.arr[x+dx[dir]][y+dy[dir]].first==0){
	temp.arr[x][y] = pii(0,0);
	x+=dx[dir];
	y+=dy[dir];
	}
	else break;
	}
	// 앞이 같은 숫자면 합쳐
	if(temp.arr[x+dx[dir]][y+dy[dir]].first == value && temp.arr[x+dx[dir]][y+dy[dir]].second==0){
	temp.arr[x+dx[dir]][y+dy[dir]].first += value;
	temp.arr[x+dx[dir]][y+dy[dir]].second = 1;
	temp.arr[x][y] = pii(0,0);
	}
	// 못합치면 정지
	else temp.arr[x][y] = pii(value,0);
	}
	}
	}
	// 위
	else if(dir==3){
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	int x = i;
	int y = j;
	if(temp.arr[x][y].first == 0) continue;
	if(temp.arr[x+dx[dir]][y+dy[dir]].first!=0 && temp.arr[x+dx[dir]][y+dy[dir]].first!=temp.arr[x][y].first) continue;
	if(temp.arr[x+dx[dir]][y+dy[dir]].second==1) continue;
	if(x+dx[dir]>=N || x+dx[dir]<0 || y+dy[dir]>=N || y+dy[dir]<0) continue;
	Move = true;
	int value = temp.arr[x][y].first;
	// 앞이 0 이면 전진
	while(x+dx[dir]<N && x+dx[dir]>=0 && y+dy[dir]<N && y+dy[dir]>=0){
	if(temp.arr[x+dx[dir]][y+dy[dir]].first==0){
	temp.arr[x][y] = pii(0,0);
	x+=dx[dir];
	y+=dy[dir];
	}
	else break;
	}
	// 앞이 같은 숫자면 합쳐
	if(temp.arr[x+dx[dir]][y+dy[dir]].first == value && temp.arr[x+dx[dir]][y+dy[dir]].second==0){
	temp.arr[x+dx[dir]][y+dy[dir]].first += value;
	temp.arr[x+dx[dir]][y+dy[dir]].second = 1;
	temp.arr[x][y] = pii(0,0);
	}
	// 못합치면 정지
	else temp.arr[x][y] = pii(value,0);
	}
	}
	}
	//아래
	else if(dir==4){
	for (int i = N-1; i >= 0; i--){
	for (int j = 0; j < N; ++j){
	int x = i;
	int y = j;
	if(temp.arr[x][y].first == 0) continue;
	if(temp.arr[x+dx[dir]][y+dy[dir]].first!=0 && temp.arr[x+dx[dir]][y+dy[dir]].first!=temp.arr[x][y].first) continue;
	if(temp.arr[x+dx[dir]][y+dy[dir]].second==1) continue;
	if(x+dx[dir]>=N || x+dx[dir]<0 || y+dy[dir]>=N || y+dy[dir]<0) continue;
	Move = true;
	int value = temp.arr[x][y].first;
	// 앞이 0 이면 전진
	while(x+dx[dir]<N && x+dx[dir]>=0 && y+dy[dir]<N && y+dy[dir]>=0){
	if(temp.arr[x+dx[dir]][y+dy[dir]].first==0){
	temp.arr[x][y] = pii(0,0);
	x+=dx[dir];
	y+=dy[dir];
	}
	else break;
	}
	// 앞이 같은 숫자면 합쳐
	if(temp.arr[x+dx[dir]][y+dy[dir]].first == value && temp.arr[x+dx[dir]][y+dy[dir]].second==0){
	temp.arr[x+dx[dir]][y+dy[dir]].first += value;
	temp.arr[x+dx[dir]][y+dy[dir]].second = 1;
	temp.arr[x][y] = pii(0,0);
	}
	// 못합치면 정지
	else temp.arr[x][y] = pii(value,0);
	}
	}
	}
	if(Move) {
	temp.cnt++;
	return temp;
	}
	else return B;
	}
	void dfs(info A){
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	A.arr[i][j].second = 0;
	ans = max(ans, A.arr[i][j].first);
	}
	}
	if(A.cnt>=5) return;
	info temp1;
	for (int i = 1; i < 5; ++i){
	temp1 = GoDirect(A,i);
	if(temp1.cnt != A.cnt) dfs(temp1);
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	info TT;
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	int num;
	cin >> num;
	TT.arr[i][j] = pii(num,0);
	}
	}
	dfs(TT);
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 12100.cpp hosted with ❤ by GitHub