<Baekjoon> #12100 BFS, Brute Force_2048(Easy) c++
Solution 1
움직일 수 있는 모든 경우의 수를selectDir[]
배열에 넣고 크기가5
가 되었을 때 각 순서대로 이동해서 최댓값을 찾아본다. 크기가5
가 되는 모든 쌍을dfs
를 통해 구한다.
- 변수 지정 (상하좌우의 방향은 차례대로
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;
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번... 이동했을 때 최댓값도 비교해주어야 한다. (하지만 결과가 같기는 하다)
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
값을 구해준다
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}
를 수행하는 식으로 한다.
(그냥 코드를 보면서 이해하는 게 빠를 거 같다.)
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 였다
Author And Source
이 문제에 관하여(<Baekjoon> #12100 BFS, Brute Force_2048(Easy) c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-12100-BFS-Brute-Force2048Easy-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)