[백준]12100_2048(Easy)

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

Solved

✔ 알고리즘 분류: 구현, 브루트포스, 시뮬레이션, 백트래킹
✔ 삼성 sw 역량 테스트스러운 문제다
✔ 데이터세팅: 보드판 세팅, 보드판 복제(원본 저장용), 블록의 수, 보드판 크기의 visit 배열(합쳐진 전적이 있는지 확인용)
✔ 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력이 목표이니 5번동안 이동할 수 있는 모든 방향의 수는 4^5=1024. 브루트포스 할만하다.
✔ 블록들을 한땀한땀 이동시키는 함수를 만든다. 알고리즘 공부 초창기에 짠거라 그런지 코드가 지저분한 것 같다.

using namespace std;
#include <iostream>
#include <cstring>

int n;
int board[21][21], cboard[21][21], visit[21][21];
int direction[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int cnt = 0;
int answer = -1;
int selected[5];

pair<int, int> getPosition(int x, int y, int num) {
	int dx = direction[num][0];
	int dy = direction[num][1];
	int ox = x, oy = y;
	while (1) {
		if ((x + dx) < 1 || (x + dx) > n || (y + dy) < 1 || (y + dy) > n) break;

		if (board[x + dx][y + dy] != 0){ //다음칸이 빈공간이 아니면 멈추기(return)
			if (visit[x + dx][y + dy] == 1) break; //이미 합쳐진 전적이 있으면 break;
			if (board[ox][oy] == board[x + dx][y + dy]) {
            //합쳐진 적이 없고 나랑 똑같다면 도착지는 이곳이니 x+=dx, y+=dy;
				x += dx;
				y += dy;
			}
			break;
		}
		x += dx;
		y += dy;
	}

	return make_pair(x, y);
}
void move(int dir) {//dir 방향으로 한칸씩 모두 움직이기
	pair<int, int> pos;
	if (dir == 2) {//남쪽으로 이동
		for (int j = n-1; j >= 1; j--) {//제일 아래 칸부터 확인
			for (int k = 1; k <= n; k++) {
            //(j,k)위치 블록이 남쪽으로 움직이면 최종 위치 pos
				pos = getPosition(j, k, dir);
				int nx = pos.first;
				int ny = pos.second;
				if (nx == j && ny == k) continue; //움직임 없다면 continue;
				if (board[nx][ny] == board[j][k] || board[nx][ny] == 0) {
                //움직임이 있다면
					if (board[nx][ny] != 0) //합치기
						visit[nx][ny] = 1;
                    //좌표 업데이트
					board[nx][ny] = board[j][k] + board[nx][ny];
					board[j][k] = 0;
				}

			}
		}
	}
	else if (dir == 0) {
		for (int j = n; j >= 1; j--) {
			for (int k = n-1; k >= 1; k--) {
				pos = getPosition(j, k, dir);
				int nx = pos.first;
				int ny = pos.second;
				if (nx == j && ny == k) continue;
				if (board[nx][ny] == board[j][k] || board[nx][ny] == 0) {
					if (board[nx][ny] != 0)
						visit[nx][ny] = 1;
					board[nx][ny] = board[j][k] + board[nx][ny];
					board[j][k] = 0;
				}
			}
		}
	}
	else if (dir == 1) {
		for (int j = 1; j <= n; j++) {
			for (int k = 2; k <= n; k++) {
				pos = getPosition(j, k, dir);
				int nx = pos.first;
				int ny = pos.second;
				if (nx == j && ny == k) continue;
				if (board[nx][ny] == board[j][k] || board[nx][ny] == 0) {
					if (board[nx][ny] != 0)
						visit[nx][ny] = 1;
					board[nx][ny] = board[j][k] + board[nx][ny];
					board[j][k] = 0;
				}

			}
		}
	}
	else if (dir == 3) {
		for (int j = 2; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				pos = getPosition(j, k, dir);
				int nx = pos.first;
				int ny = pos.second;
				if (nx == j && ny == k) continue;
				if (board[nx][ny] == board[j][k] || board[nx][ny] == 0) {
					if (board[nx][ny] != 0)
						visit[nx][ny] = 1;
					board[nx][ny] = board[j][k] + board[nx][ny];
					board[j][k] = 0;
				}
			}
		}
	}

}


int findMax() {
	int a = -1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a < board[i][j]) a = board[i][j];
		}
	}
	return a;
}

void copyBoard(int a[][21], int b[][21]) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			b[i][j] = a[i][j];
		}
	}
	return;
}



void solve(int cnt) {
	if (cnt == 5) {
		for (int i = 0; i < 5; i++) {
			move(selected[i]);
			memset(visit, 0, sizeof(visit));
 			for (int i = 1; i <= n; i++) {
				memset(visit[i], 0, sizeof(visit[i]));
			}
		}
		//maxvalue
		int temp = findMax();
		answer = temp > answer ? temp : answer;
		copyBoard(cboard, board);
		return;
	}

	for (int i = 0; i < 4; i++) {
		selected[cnt] = i;
		solve(cnt+1);
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> board[i][j];
			if (board[i][j] != 0) cnt++;
		}
	}
	copyBoard(board, cboard);
	solve(0);
	cout << answer << '\n';
}