백준: 2048(12100번)
알고리즘 문제 해결 과정을 기록합니다
· 5 min read
문제 개요 #
- Source: 백준 링크
- Difficulty: Gold 1
- Key Concept: DFS
접근 방법 #
2048은 좌우상하로 슬라이드 하면서 숫자들을 합치므로 DFS를 바로 떠올릴 수 있었습니다. 보드의 숫자를 4 방향으로 이동시키는 로직과 숫자를 합치는 로직 2가지로 나누어 접근하였습니다. 숫자를 4 방향으로 이동시키는 것은 각 방향은 끝 행 또는 열을 기준을 삼아 기준이 되는 그 다음 행 또는 열부터 기준이 되는 방향으로 이동시켰습니다. 이 후 기존에 다른 숫자가 있으면서 그 수가 같다면 합침과 동시에 2배로 만들었고, 수가 다르다면 그 수 전까지만 이동시켰습니다.
시행착오 #
고려하지 못한 조건이 숫자들을 움직일 때 합쳐지는건 슬라이드 당 한번만 가능하다는 조건이었습니다.
즉 4 2 2라는 숫자들을 왼쪽으로 슬라이드 했을 때 2 2가 합쳐져 4가 되어 4 4 0의 형태로 유지가 되어야 합니다.
하지만 해당 조건을 고려하지 않은 로직을 짜버려 8 0 0으로 즉 숫자가 2번 움직이게 되었습니다.
해결 방법 #
bool vis[30][30]을 통해 슬라이드 할 때마다 해당 숫자의 움직임 여부를 파악하고 만약 이미 움직인 수라면 중복하여 움직이지 않도록 하였습니다.
이를 통해 한 번의 슬라이ㄴ에서는 한 번의 합침 과정만 남아 중복 합침 현상을 없앨 수 있었습니다.
슬라이드마다 해당 배열을 초기화해야 했기 때문에 memset을 이용하여 쉽게 배열을 반복마다 초기화 할 수 있었습니다.
#include <bits/stdc++.h>
using std::pair;
using std::string;
using std::vector;
void setup_io() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
}
constexpr int LIMIT = 5;
vector<int> v;
int board[30][30], t_board[30][30];
bool vis[30][30];
int answer = 0, n;
// 이동
void moveNumbers(int board[30][30], int dir) {
if (dir == 0) { // 상으로 움직임
int bsize = n;
for (int r = 1; r < bsize; ++r) {
// 최 상단이 아닌 행
for (int c = 0; c < bsize; c++) {
if (board[r][c] == 0) {
continue;
}
int t = 1;
while (r - t >= 0 &&
!board[r - t][c]) { // 칸이 비지 않을 때 까지 이동
t++;
}
int temp = board[r][c];
board[r][c] = 0;
if (board[r - t][c] == temp && !vis[r - t][c]) {
board[r - t][c] *= 2;
vis[r - t][c] = true;
continue;
}
board[r - t + 1][c] = temp;
}
}
} else if (dir == 1) {
// 하로 이동
for (int r = n - 2; r >= 0; --r) {
// 최 상단이 아닌 행
for (int c = 0; c < n; c++) {
if (board[r][c] == 0) {
continue;
}
int t = 1;
while (r + t < n &&
!board[r + t][c]) { // 칸이 비지 않을 때 까지 이동
t++;
}
int temp = board[r][c];
board[r][c] = 0;
if (board[r + t][c] == temp && !vis[r + t][c]) {
board[r + t][c] *= 2;
vis[r + t][c] = true;
continue;
}
board[r + t - 1][c] = temp;
}
}
} else if (dir == 2) {
// 좌로 이동
for (int c = 1; c < n; c++) {
for (int r = 0; r < n; r++) {
if (board[r][c] == 0) {
continue;
}
int t = 1;
while (c - t >= 0 && !board[r][c - t]) {
t++;
}
int temp = board[r][c];
board[r][c] = 0;
if (board[r][c - t] == temp && !vis[r][c - t]) {
board[r][c - t] *= 2;
vis[r][c - t] = true;
continue;
}
board[r][c - t + 1] = temp;
}
}
} else if (dir == 3) {
// 우로 이동
for (int c = n - 2; c >= 0; c--) {
for (int r = 0; r < n; r++) {
if (board[r][c] == 0) {
continue;
}
int t = 1;
while (c + t < n && !board[r][c + t]) {
t++;
}
int temp = board[r][c];
board[r][c] = 0;
if (board[r][c + t] == temp && !vis[r][c + t]) {
board[r][c + t] *= 2;
vis[r][c + t] = true;
continue;
}
board[r][c + t - 1] = temp;
}
}
}
}
// 보드 탐색
int getMaximumNum() {
int result = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
result = std::max(result, t_board[r][c]);
}
}
return result;
}
// 완전 탐색을 이용
void dfs(int depth) {
if (depth >= LIMIT) { // 5번 모두 이동 시
// 순서대로 모두 이동
std::memcpy(t_board, board, sizeof(board));
for (const int& item : v) {
std::memset(vis, 0, sizeof(vis));
moveNumbers(t_board, item);
}
// 보드의 최대값 탐색
answer = std::max(answer, getMaximumNum());
return;
}
for (int i = 0; i < 4; i++) { // 상하좌우
v.emplace_back(i); // 이동 시킴?
dfs(depth + 1); // 다음 단계 진입
v.pop_back();
}
return;
}
void getInput() {
std::cin >> n;
int t;
for (std::size_t i = 0; i < n; ++i) {
for (std::size_t j = 0; j < n; ++j) {
std::cin >> t;
board[i][j] = t;
}
}
}
// -----------------------------------------------------------
int solution() {
// 여기에 문제 풀이 코드를 작성하세요.
getInput();
dfs(0);
return answer;
}
int main(int argc, char** argv) {
setup_io();
int t = 1;
// cin >> t; // 여러 테스트 케이스를 위한 코드
while (t--) {
std::cout << solution();
}
return 0;
}
알고리즘 설명 #
입력받은 보드의 크기와 보드의 원소들을 바탕으로 DFS를 하였습니다.
이 때 for문의 i는 방향을 나타내고 0,1,2,3이 순서대로 상하좌우를 의미합니다.
이동 횟수는 문제에서 5번이라는 조건을 걸었기 때문에 const int LIMIT은 5로 고정 후 슬라이딩 5번 이후에는 직접 보드를 움직여 결과를 확인하도록 하였습니다.
임시 보드판을 memcpy를 통해 board의 원소들을 모두 t_baord에 복사한 뒤
움직일 때마다 vis(합침 여부)를 모두 false로 초기화시키면서 5번의 이동을 시뮬레이션 하였습니다.
이동 시 빈칸이 없을 때까지 해당 숫자를 기준이 되는 방향으로 이동시킨 뒤 기존 숫자의 위치의 t_baord값은 0으로 바꾼 후 합침 여부를 판단한 뒤 합친다면 수를 2배로 한 뒤 vis를 통해 그 기록을 남깁니다.
이 후 5번의 이동이 끝난 뒤 t_board를 검사하여 최댓값이 기존의 값보다 크다면 answer값을 변경합니다.
이렇게 상하좌우 중 하나를 골라 5번을 이동시키는 모든 경우의 수를 반복하여 그 중 만들 수 있는 최대값이 answer에 할당이 되어 solution에서 리턴하게 됩니다.
성능 분석 #
- Time Complexity: $O(N^2)$
핵심 정리 #
DFS를 구조화하는 것은 비교적 간단하였으나 2048이라는 게임의 모든 조건을 만족시키면서 슬라이딩을 구현하는 것이 예상보다 까다로웠습니다. 문제를 꼼꼼히 읽지 않아 합침 중복의 문제를 제대로 확인하지 않아서 많은 시간을 허비하게 되었습니다. 해당 문제를 통해 배경 지식이 있는 부분이더라도 꼼꼼히 문제의 조건들을 확인할 필요성을 느꼈습니다.