[ BOJ ] 12100. 2048 (Easy)

문제 링크

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

 

종류

DFS + 시뮬레이션

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 20
using namespace std;

int N, Answer = 0;
int origin[MAX][MAX];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

void input()
{
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> origin[i][j];
        }
    }
}

void copy_map(int board[MAX][MAX], int map[MAX][MAX])
{
    for(int r = 0; r < N; r++)
    {
        for(int c = 0; c < N; c++)
        {
            board[r][c] = map[r][c];
        }
    }
}

void calculate(int board[MAX][MAX])
{
    int num = 0;
    for(int r = 0; r < N; r++)
    {
        for(int c = 0; c < N; c++)
        {
            num = max(board[r][c], num);
        }
    }
    Answer = max(Answer, num);
}

void DFS(int map[MAX][MAX], int dir, int cnt)
{
    int board[MAX][MAX];
    
    copy_map(board, map);
    
    if(dir == 0) // 상
    {
        for(int c = 0; c < N; c++)
        {
            vector<pair<int, bool>> v;
            for(int r = 0; r < N; r++)
            {
                if(board[r][c] == 0) continue;
                
                if(v.size() == 0)
                {
                    v.push_back(make_pair(board[r][c], false));
                }
                else if(v.back().first == board[r][c] && v.back().second == false)
                {
                    v.back().first *= 2;
                    v.back().second = true;
                }
                else
                {
                    v.push_back(make_pair(board[r][c], false));
                }
                
                board[r][c] = 0;
            }
            
            for(int i = 0; i < v.size(); i++)
            {
                board[i][c] = v[i].first;
            }
        }
    }
    else if(dir == 1) // 하
    {
        for(int c = 0; c < N; c++)
        {
            vector<pair<int, bool>> v;
            for(int r = N-1; r >= 0; r--)
            {
                if(board[r][c] == 0) continue;
                
                if(v.size() == 0)
                {
                    v.push_back(make_pair(board[r][c], false));
                }
                else if(v.back().first == board[r][c] && v.back().second == false)
                {
                    v.back().first *= 2;
                    v.back().second = true;
                }
                else
                {
                    v.push_back(make_pair(board[r][c], false));
                }
                
                board[r][c] = 0;
            }
            
            for(int i = 0; i < v.size(); i++)
            {
                board[(N-1)-i][c] = v[i].first;
            }
        }
    }
    else if(dir == 2) // 좌
    {
        for(int r = 0; r < N; r++)
        {
            vector<pair<int, bool>> v;
            for(int c = 0; c < N; c++)
            {
                if(board[r][c] == 0) continue;
                
                if(v.size() == 0)
                {
                    v.push_back(make_pair(board[r][c], false));
                }
                else if(v.back().first == board[r][c] && v.back().second == false)
                {
                    v.back().first *= 2;
                    v.back().second = true;
                }
                else
                {
                    v.push_back(make_pair(board[r][c], false));
                }
                
                board[r][c] = 0;
            }
            
            for(int i = 0; i < v.size(); i++)
            {
                board[r][i] = v[i].first;
            }
        }
    }
    else if(dir == 3) // 우
    {
        for(int r = 0; r < N; r++)
        {
            vector<pair<int, bool>> v;
            for(int c = N-1; c >= 0; c--)
            {
                if(board[r][c] == 0) continue;
                
                if(v.size() == 0)
                {
                    v.push_back(make_pair(board[r][c], false));
                }
                else if(v.back().first == board[r][c] && v.back().second == false)
                {
                    v.back().first *= 2;
                    v.back().second = true;
                }
                else
                {
                    v.push_back(make_pair(board[r][c], false));
                }
                
                board[r][c] = 0;
            }
            
            for(int i = 0; i < v.size(); i++)
            {
                board[r][(N-1)-i] = v[i].first;
            }
        }
    }
    
    if(cnt == 5)
    {
        calculate(board);
        return;
    }
    
    for(int i = 0; i < 4; i++)
    {
        DFS(board, i, cnt+1);
    }
}

void solve()
{
    for(int i = 0; i < 4; i++)
    {
        DFS(origin, i, 1);
    }
    cout << Answer << endl;
}

int main()
{
    input();
    solve();
    return 0;
}

 

리뷰

52분 소요

 

예전에 몇 시간동안 풀었는데도 해결하지 못한 문제를 50분만에 해결해서 뿌듯 !

 

더 빨리 풀 수 있었는데 놓친 부분은 바로..! 배열을 함수의 매개변수로 보낼 때, 주소로 전달되기 때문에 실제 배열 값이 계속해서 변경된다는 것!이다. [ 참고 글 ]

분명 저학년 때 배웠던 개념인데 (포인터와 배열 ^^) 깜빡하고 있었다. ㅎ... 지금이라도 다시 리뷰해서 다행이다.

 

DFS함수에서 이차원 배열을 매개변수로 받아서 퍼즐을 이동시키고, 다시 그 이차원 배열을 매개변수로 전달하였었다. 분명 백트레킹을 하였는데 이전 배열의 값이 아니라 변경된 값들이었다. 아 배열은 값의 전달이 아니라 주소의 전달이지 ...ㅎ 함수 내에서 이차원 배열을 새로 선언하고 매개변수 배열값을 복사시킨 후 이동시켜서 바로 해결할 수 있었다.

 

만약 DFS로 백트레킹하면서 이차원 배열의 값을 변경하는 것이 아니라, 이동 경로를 미리 정해두고 쭉 진행하였더라면 매개변수로 받은 이차원 배열을 그대로 사용해도 된다. 하지만 그럼 시간이 더 오래걸리겠쥬..?