<Baekjoon> #12100 BFS, Brute Force_2048(Easy) c++

Google 아니고 Joogle·2022년 2월 17일
"삼성SW"BFSalgorithmbaekjoonbruteforce
0

SAMSUNG SW Test

목록 보기
6/39
post-thumbnail

#12100 2048 Game
참고1 참고2

Solution 1
움직일 수 있는 모든 경우의 수를 selectDir[] 배열에 넣고 크기가 5가 되었을 때 각 순서대로 이동해서 최댓값을 찾아본다. 크기가 5가 되는 모든 쌍을 dfs를 통해 구한다.

  1. 변수 지정 (상하좌우의 방향은 차례대로 0,1,2,3)
const int UP = 0;
const int DOWN = 1;
const int LEFT = 2;
const int RIGHT = 3;

vector<vector<int>> board;
int selectDir[5]; // direction order
int N; // board size
int maxNum=0;
  1. selectDir을 만들기 위해서는 순열의 조합을 만드는 dfs함수 를 구현해야 한다.
void selectOrder(int cnt) {
	if (cnt == 5) {
		startGame();
		return;
	}
	for (int i = 0; i < 4; i++) {
		selectDir[cnt] = i;
		selectOrder(cnt+1);
	}
}
  • 먼저 selectDir[]에 {0,0,0,0,0}이 저장되었을 때 이 크기가 5가 되었으므로startGame()함수를 호출하여 각 방향마다 차례대로 움직인다.
  • 끝나고 나면 다시 {0,0,0,0,1}이 저장되어 startGame()을 호출하여 각 방향마다 차례대로 움직인다.
  • 여기서 치명적인 단점 2가지가 있는데 {0,0,0,0,0}과 {0,0,0,0,1} 에서 처음 4번의 움직임은 0즉, 위로 움직이는 것으로 똑같지만 이 반복된 연산을 따로 2번 수행하게 된다.
  • 그리고 문제에서 5번을 이동했을 때 최댓값을 구하는 것이 아니라 최대 5번을 이동할 수 있다고 했으므로 1번, 2번... 이동했을 때 최댓값도 비교해주어야 한다. (하지만 결과가 같기는 하다)
  1. startGame()
void startGame() {

	//copy board
	vector<vector<int>> Cboard;
	Cboard.assign(board.size(), vector<int>(board.size()));
	copy(board.begin(), board.end(), Cboard.begin());

	for (int i = 0; i < 5; i++) {
		int dir = selectDir[i];
		switch (dir) {
		case UP: moveUp(Cboard); break;
		case DOWN: moveDown(Cboard); break;
		case LEFT: moveLeft(Cboard); break;
		case RIGHT: moveRight(Cboard); break;
		}
	}
	getMax(Cboard);
}
  • 원래 board는 변하면 안 되므로 copy board인 vector Cboard를 만들어 전체 복사
  • selectDir[] 에 들어왔던 순서대로 움직이고 총 5번의 움직임이 끝났을 때 Cboard에 있는 max 값을 구해준다
  1. moveRight() - 대표로 오른쪽으로 움직이는 연산만 본다
  • i는 현재 몇 번째 행인가를 나타낸다
  • j는 N-2에서 시작하고 k는 j보다 하나 큰 수에서 시작한다
  • 그림에서는 i=0, i=3 인 경우를 예시로 들었는데 i=0일 때, 인접한 두 수가 같다면 더 뒤에 있는 수에 2배를 해주고 원래 있던 자리는 0으로 바꾸어 준다. 이때 visited를 두어 이 자리가 이미 한 번 변경되었다는 표시를 해준다.
  • i=3인 경우 k가 0이므로 앞에 있는 수 (k-1 위치에 있는 2)를 가져오고 k-1은 0으로 바꾸어 준다. 이 과정을 수행하면 {2,0,2,0,2}가 되고 다시 j는 Cboard[3][2]를, k는 Cboard[3][3]을 가리키고 k가 0이므로 다시 k-1위치에 있는 값을 가져온다. {2,0,0,2,2}가 되고 k는 Cboard[3][4]를 가리키고 위에 else if 문에 걸리게 되어 합쳐지는 연산을 수행한다.
  • 현재 가리키고 있는 k값이 0 이어서 앞에 있는 값을 가져오면 계속 연산을 이어나가고 그렇지 않으면 break하여 j값을 다시 앞으로 이동하여 연산을 반복한다.
void moveRight(vector<vector<int>>& Cboard) {
	vector<vector<bool>> visited(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++) {
		for (int j = N - 2; j >= 0; j--) {
			if (Cboard[i][j] == 0) continue;
			for (int k = j + 1; k < N; k++) {
				if (Cboard[i][k] == 0) {
					Cboard[i][k] = Cboard[i][k - 1];
					Cboard[i][k - 1] = 0;
				}
				else if (Cboard[i][k] == Cboard[i][k - 1] && !visited[i][k]) {
					Cboard[i][k] *= 2;
					Cboard[i][k - 1] = 0;
					visited[i][k] = true;
					break;
				}
				else break;
			}
		}
	}
}

전체코드

#include <iostream>
#include <vector>

using namespace std;
const int UP = 0;
const int DOWN = 1;
const int LEFT = 2;
const int RIGHT = 3;

vector<vector<int>> board;
int selectDir[5]; // direction order
int N; // board size
int maxNum=0;

void moveUp(vector<vector<int>>& Cboard) {
	vector<vector<bool>> visited(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++) {
		for (int j = 1; j <N; j++) {
			if (Cboard[j][i] == 0) continue;
			for (int k = j -1; k >=0; k--) {
				if (Cboard[k][i] == 0) {
					Cboard[k][i] = Cboard[k + 1][i];
					Cboard[k + 1][i] = 0;
				}
				else if (Cboard[k][i] == Cboard[k + 1][i] && !visited[k][i]) {
					Cboard[k][i] *= 2;
					Cboard[k + 1][i] = 0;
					visited[k][i] = true;
					break;
				}
				else break;
			}
		}
	}
}

void moveDown(vector<vector<int>>& Cboard) {
	vector<vector<bool>> visited(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++) {
		for (int j = N - 2; j >= 0; j--) {
			if (Cboard[j][i] == 0) continue;
			for (int k = j + 1; k < N; k++) {
				if (Cboard[k][i] == 0) {
					Cboard[k][i] = Cboard[k - 1][i];
					Cboard[k - 1][i] = 0;
				}
				else if (Cboard[k][i] == Cboard[k - 1][i] && !visited[k][i]) {
					Cboard[k][i] *= 2;
					Cboard[k - 1][i] = 0;
					visited[k][i] = true;
					break;
				}
				else break;
			}
		}
	}
}

void moveLeft(vector<vector<int>>& Cboard) {
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	
	for (int i = 0; i < N; i++) {
		for (int j = 1; j < N; j++) {
			if (Cboard[i][j] == 0) continue;
			for (int k = j - 1; k >= 0; k--) {
				if (Cboard[i][k] == 0) {
					Cboard[i][k] = Cboard[i][k + 1];
					Cboard[i][k + 1] = 0;
				}
				else if (Cboard[i][k] == Cboard[i][k + 1] && !visited[i][k]) {
					Cboard[i][k] *= 2;
					Cboard[i][k +1] = 0;
					visited[i][k] = true;
					break;
				}
				else break;
			}
		}
	}
}

void moveRight(vector<vector<int>>& Cboard) {
	vector<vector<bool>> visited(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++) {
		for (int j = N - 2; j >= 0; j--) {
			if (Cboard[i][j] == 0) continue;
			for (int k = j + 1; k < N; k++) {
				if (Cboard[i][k] == 0) {
					Cboard[i][k] = Cboard[i][k - 1];
					Cboard[i][k - 1] = 0;
				}
				else if (Cboard[i][k] == Cboard[i][k - 1] && !visited[i][k]) {
					Cboard[i][k] *= 2;
					Cboard[i][k - 1] = 0;
					visited[i][k] = true;
					break;
				}
				else break;
			}
		}
	}
}

void  getMax(vector<vector<int>>& Cboard) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			maxNum = max(maxNum, Cboard[i][j]);
}

void startGame() {

	//copy board
	vector<vector<int>> Cboard;
	Cboard.assign(board.size(), vector<int>(board.size()));
	copy(board.begin(), board.end(), Cboard.begin());

	for (int i = 0; i < 5; i++) {
		int dir = selectDir[i];
		switch (dir) {
		case UP: moveUp(Cboard); break;
		case DOWN: moveDown(Cboard); break;
		case LEFT: moveLeft(Cboard); break;
		case RIGHT: moveRight(Cboard); break;
		}
	}
	getMax(Cboard);
}

void selectOrder(int cnt) {
	if (cnt == 5) {
		startGame();
		return;
	}
	for (int i = 0; i < 4; i++) {
		selectDir[cnt] = i;
		selectOrder(cnt+1);
	}
}

void initBoard() {
	cin >> N;
	board = vector<vector<int>>(N, vector<int>(N));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];
}

int main() {
	initBoard();
	selectOrder(0);

	cout << maxNum << endl;
	
	return 0;
}

Solution 2
앞에서 풀었던 문제의 단점 2가지를 해결
이 방법에서는 5번째가 되었을 때 최댓값을 구하는 것이 아니라 매번 구하고, 반복되는 움직임은 한 번만 수행한다. 그리고 board를 copy하지 않고 현재 보드판에서 그대로 움직였다가 return 하는 방식을 사용한다.

예를들어 {0,0,0,0,0}의 움직임을 수행한 보드판이 있으면 {0,0,0,0]까지 수행한 보드판을 가지고 다음 연산인 {1} 을 수행하고, 다시 {0,0,0,0} 보드판을 가지고 {2}를 수행하는 식으로 한다.
(그냥 코드를 보면서 이해하는 게 빠를 거 같다.)

  1. dfs 함수 
void dfs(int cnt, vector<vector<int>> board) {
	answer = max(answer, getMax(board));
	if (cnt == 5) return;

	dfs(cnt + 1, moveUp(board));
	dfs(cnt + 1, moveDown(board));
	dfs(cnt + 1, moveLeft(board));
	dfs(cnt + 1, moveRight(board));
}
  • 앞서 말했듯이 매번 dfs 함수가 호출 될 때마다 최댓값 갱신을 한다.
  • 처음에 dfs(0, board)를 호출하면 up, up, up, up, up 5번의 연산을 수행하고 return 되어 up up up up 보드를 가지고 dfs (cnt+1, moveDown(board))를 호출한다

2.moveRight 

vector<vector<int>> moveRight(vector<vector<int>> board) {
......
......
......
return board;
}
  • 위에서 만든 움직이는 원리는 동일하지만 반환형이 다르다 (왜 이렇게 되어야 하는지 이 부분을 잘 이해해야 한다)

전체 코드

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

using namespace std;

int answer;
int N;

vector<vector<int>> moveUp(vector<vector<int>> board) {
	vector<vector<bool>> changed(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++) {
		for (int j = 1; j < N; j++) {
			if (board[j][i] == 0) continue;
			for (int k = j - 1; k >= 0; k--) {

				if (board[k][i] == board[k + 1][i] && !changed[k][i]) {
					board[k][i] *= 2;
					board[k + 1][i] = 0;
					changed[k][i] = true;
					break;
				}

				else if (board[k][i] == 0) {
					board[k][i] = board[k + 1][i];
					board[k + 1][i] = 0;
				}
				else break;
			}
		}
	}
	return board;
}

vector<vector<int>> moveDown(vector<vector<int>> board) {
	vector<vector<bool>> changed(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++) {
		for (int j = N - 2; j >= 0; j--) {
			if (board[j][i] == 0) continue;
			for (int k = j + 1; k < N; k++) {
				if (board[k][i] == board[k - 1][i] && !changed[k][i]) {
					board[k][i] *= 2;
					board[k - 1][i] = 0;
					changed[k][i] = true;
					break;
				}
				else if (board[k][i] == 0) {
					board[k][i] = board[k - 1][i];
					board[k - 1][i] = 0;
				}
				else break;
			}
		}
	}
	return board;
}

vector<vector<int>> moveLeft(vector<vector<int>> board) {
	vector<vector<bool>> changed(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++) {
		for (int j = 1; j < N; j++) {
			if (board[i][j] == 0) continue;
			for (int k = j - 1; k >= 0; k--) {

				if (board[i][k] == board[i][k + 1] && !changed[i][k]) {
					board[i][k] *= 2;
					board[i][k + 1] = 0;
					changed[i][k] = true;
					break;
				}

				else if (board[i][k] == 0) {
					board[i][k] = board[i][k + 1];
					board[i][k + 1] = 0;
				}
				else break;
			}
		}
	}
	return board;
}

vector<vector<int>> moveRight(vector<vector<int>> board) {
	vector<vector<bool>> changed(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++) {
		for (int j = N - 2; j >= 0; j--) {
			if (board[i][j] == 0) continue;

			for (int k = j + 1; k < N; k++) {
				if (board[i][k] == board[i][k - 1] && !changed[i][k]) {
					board[i][k] *= 2;
					board[i][k - 1] = 0;
					changed[i][k] = true;
					break;
				}

				else if (board[i][k] == 0) {
					board[i][k] = board[i][k - 1];
					board[i][k - 1] = 0;
				}
				else break;
			}
		}
	}
	return board;
}

int getMax(vector<vector<int>> board) {
	int maxNum = 0;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			maxNum = max(maxNum, board[i][j]);
	return maxNum;
}
void dfs(int cnt, vector<vector<int>> board) {
	answer = max(answer, getMax(board));
	if (cnt == 5) return;

	dfs(cnt + 1, moveUp(board));
	dfs(cnt + 1, moveDown(board));
	dfs(cnt + 1, moveLeft(board));
	dfs(cnt + 1, moveRight(board));
}
int main() {

	cin >> N;
	vector<vector<int>> board(N, vector<int>(N));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];
	dfs(0, board);
	cout << answer << endl;

	return 0;
}

너무 힘들고 까다로웠던 문제고 첫 번째와 두 번째 시간 차이는 12ms 였다

profile
Google 아니고 Joogle
Backend 개발자 지망생
이전 포스트

<Baekjoon> #14891 Deque_톱니바퀴 c++

다음 포스트

<Baekjoon> #20056 마법사 상어와 파이어볼 c++

0개의 댓글