[백준 12100] 2048(Easy)

티스토리 뷰

BOJ

[백준 12100] 2048(Easy)

wo_ody 2020. 2. 29. 16:27

안녕하세요 !!! 우디 ✨ 입니다 .

오늘은 DFS 로 푸는 2048(Easy) 을 설명해드릴께요 ~

문제

BOJ 12100번 2048(Easy) 바로가기

문제 설명

이 문제의 핵심은

DFS로 순환구조 잡기
상 하 좌 우 옮기는 작업

이 두가지만 기억하고 문제를 풀면 됩니다 ! (말로는 참 간단하죠 ,,?^^)

우선, 이 문제가 왜 DFS 로 접근해야 하는지 설명해드리겠습니다.


xxxxxxxxxx
보드를 최대 5번까지 움직일 수 있고, 움직이는 방향은 상,하,좌,우 총 4가지 입니다.

따라서 5번 동안 상,하,좌,우 이 4방향을 중복이 가능하게 나열을 해야합니다.

(또한, 최대 5번 이므로 1번을 움직여서 최대가 나올 수 있고 2번을 움직여서 최대가 나올 수 있는 등 예측하지 못하기 때문에 한번 이동했을 때마다 전체 배열을 순회하여 최댓값을 갱신해주는 작업이 필요합니다.)

➀ 트리🌳

➁ 휴도 코드 👍


x
void DFS(int direction, int num)//direction 0:상,1:하,2:좌,3:우 / num은 순번
{
    biggest(arr);//방향 한번 움직일때마다 최댓값 갱신해주기
    if(num>4) return;//최대 5번까지만
    int tmp[21][21];
    tmp<-arr;//전의 배열 상태 저장해줌
    
    for(int i=0;i<4;i++)
    {
        if(i==0) UP();
        else if(i==1) DOWN();
        else if(i==2) RIGHT();
        else if(i==3) LEFT();
        
        DFS(i,num+1);//다음 순서 돌아주세여 ~
        arr<-tmp;//각 방향마다 arr이 갱신되므로 다음 방향을 위해서 arr 전 상태로 복귀시켜줌
    }
}

다음으로, 각 방향마다 옮기는 작업을 어떤 구조로 했는지 알려드리겠습니다.

상,화,좌,우 각 함수 모두 구조는 똑같고 안의 배열을 순회할 때 index만 달라지므로 상 함수를 예로 들어 설명하겠습니다.


x
void UP()
{
    int index=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(arr[j][i]!=0)//현재 지점이 0이거나 아닌걸로 나눔.현재지점이 0이면 계속 for문 
            { 
                if(j==(n-1))//마지막까지 왔음
                {
                    arr[index][i]=arr[j][i];
                    if(index!=j)arr[j][i]=0;
                }
                else if(arr[j+1][i]==0)//현재다음 지점이 0임. for문 돌아서 같은 것 있는지 없는지                                                                                       확인
                {
                    for(int z=j+1;z<n;z++)
                    {
                        if(arr[z][i]==arr[j][i])
                        {
                            arr[index][i]=2*arr[j][i];
                            if(index!=j) 
                            {
                                arr[j][i]=0;
                                arr[z][i]=0;
                            }//현재지점 j와 index가 다르면 현재지점과 z지점(for문 돌아서 같은 거                                발견한 지점)을 0으로 초기화 시켜줘야함
                            else arr[z][i]=0;//현재지점 j와 index가 같아서 z지점만 초기화
                            index++;    
                            j=z;//같은 것 만난 지점 이후로만 보면됨
                            break;//z for문 빠져나가야 함
                        }
                        else if(arr[z][i]!=arr[j][i] && arr[z][i]!=0)//0이 아니면서 다른 것
                        {
                            arr[index][i]=arr[j][i];
                            if(index!=j) arr[j][i]=0;
                            index++;
                            break;//z for문 빠져나가야 함
                        }
                        else if(z==(n-1))//끝에 왔는데 같은 것도 없고 다른것도 없다. 고로 0뿐
                        {
                            arr[index][i]=arr[j][i];
                            if(index!=j) arr[j][i]=0;
                            index++;
                        }
                    }
                }
                else//현재 다음 지점이 0이 아님.
                {
                    if(arr[j+1][i]==arr[j][i])
                    {
                        arr[index][i]=2*arr[j][i];
                        if(index!=j)
                        {
                            arr[j][i]=0;
                            arr[j+1][i]=0;
                        }
                       else arr[j+1][i]=0;
                        index++;
                        j++;
                    }
                    else
                    {
                        arr[index][i]=arr[j][i];
                        if(index!=j) arr[j][i]=0;
                        index++;
                    }
                }
            }//현재지점이 0아님
            
        }//j for문 끝
        index=0;//한 줄씩 배열을 옮기므로 한 줄이 끝날때마다 index 초기화
    }
}

구현


#include <iostream>
#include <algorithm>
using namespace std;
int n;
int maxx = 0;
int arr[21][21];
void copy(int to[21][21], int from[21][21]);
void dfs(int dir, int num);
void biggest(int arr[21][21]);
void print(int arr[21][21]);
void up();
void down();
void left();
void right();
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
    dfs(0, 0);
    cout << maxx << endl;
}
void dfs(int dir, int num)
{
    // cout << "방향 : " << dir << " " << num << " 번째" << endl;
    biggest(arr);
    if (num > 4) return;//끝냄
    int tmp[21][21];
    copy(tmp, arr);
    for (int i = 0; i < 4; i++)
    {
        if (i == 0) up();
        if (i == 1) down();
        if (i == 2) left();
        if (i == 3) right();
        //arr에서 max 값 뽑아주기
        biggest(arr);
        dfs(i, num + 1);
        copy(arr, tmp);
    }
}
void up()
{
    int index = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[j][i] != 0)
            {
                if (j == (n - 1))
                {
                    arr[index][i] = arr[j][i];
                    if(index!=j)arr[j][i] = 0;
                    
                }
                else if (arr[j + 1][i] == 0)
                {
                    for (int z = j + 1; z < n; z++)
                    {
                        if (arr[z][i] == arr[j][i])
                        {
                            arr[index][i] = 2 * arr[j][i];
                            if (index == j)
                                arr[z][i] = 0;
                            else {
                                arr[z][i] = 0;
                                arr[j][i] = 0;
                            }//해당 배열 0으로 바꿔주기(합쳐줬으니깐)
                            index++;
                            j = z;
                            break;
                        }//같은 것 만남
                        else if (arr[z][i] != arr[j][i] && arr[z][i]!=0)
                        {
                            arr[index][i] = arr[j][i];
                            if (index != j) arr[j][i] = 0;
                            index++;
                            break;
                        }//다른 것 만남
                        else if (z == (n - 1))
                        {
                            arr[index][i] = arr[j][i];
                            if (index != j)// index < j
                            {
                                arr[j][i] = 0;
                            }
                            index++; //같은 것 안만나면 그대로 적재후 index++
                        }
                    }
                }
                else if (arr[j + 1][i] != 0)
                {
                    if (arr[j][i] == arr[j + 1][i])
                    {
                        arr[index][i] = 2 * arr[j][i];
                        if (index != j)
                        {
                            arr[j][i] = 0;
                            arr[j + 1][i] = 0;
                        }
                        else
                        {
                            arr[j + 1][i] = 0;
                        }
                        index++;
                        j++;
                    }//뒤에것이랑 같음 
                    else
                    {
                        arr[index][i] = arr[j][i];
                        if (index != j) arr[j][i] = 0;
                        index++;//뒤에 것이랑 같지 않으면 그대로 적재 후 index++
                    }
                }
            }
        }
        index = 0;
    }
    //cout << "상" << endl;
    //print(arr);
    //cout << endl;
}
void down()
{
    int index = n - 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = n - 1; j > -1; j--)
        {
            if (arr[j][i] != 0)
            {
                if (j == 0)
                {
                    arr[index][i] = arr[j][i];
                    if(index!=j)arr[j][i] = 0;
                    
                }
                else if (arr[j - 1][i] == 0)
                {
                    for (int z = j - 1; z > -1; z--)
                    {
                        if (arr[z][i] == arr[j][i])
                        {
                            arr[index][i] = 2 * arr[j][i];
                            if (index == j) arr[z][i] = 0;
                            else {
                                arr[z][i] = 0;
                                arr[j][i] = 0;
                            }//해당 배열 0으로 바꿔주기(합쳐줬으니깐)
                            index--;
                            j = z;
                            break;
                        }//같은 것 만남
                        else if (arr[z][i] != arr[j][i] && arr[z][i]!=0)
                        {
                            arr[index][i] = arr[j][i];
                            if (index != j) arr[j][i] = 0;
                            index--;
                            break;
                        }//다른 것 만남
                        else if (z == 0)
                        {
                            arr[index][i] = arr[j][i];
                            if (index != j) arr[j][i] = 0;
                            index--;//같은 것 안만나면 그대로 적재후 index++
                        }
                    }
                }
                else if (arr[j - 1][i] != 0)
                {
                    if (arr[j][i] == arr[j - 1][i])
                    {
                        arr[index][i] = 2 * arr[j][i];
                        if (index != j)
                        {
                            arr[j][i] = 0;
                            arr[j - 1][i] = 0;
                        }
                        else arr[j - 1][i] = 0;
                        index--;
                        j--;
                    }//뒤에것이랑 같음 
                    else
                    {
                        arr[index][i] = arr[j][i];
                        if (index != j) arr[j][i] = 0;
                        index--;//뒤에 것이랑 같지 않으면 그대로 적재 후 index++
                    }
                }
            }
        }
        index = n - 1;
    }
    //cout << "하" << endl;
    //print(arr);
    //cout << endl;
}
void left()
{
    int index = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] != 0)
            {
                if (j == (n - 1))
                {
                    arr[i][index] = arr[i][j];
                    if(index!=j) arr[i][j] = 0;
                    
                }
                else if (arr[i][j + 1] == 0)
                {
                    for (int z = j + 1; z < n; z++)
                    {
                        if (arr[i][z] == arr[i][j])
                        {
                            arr[i][index] = 2 * arr[i][j];
                            if (index == j) arr[i][z] = 0;
                            else {
                                arr[i][z] = 0;
                                arr[i][j] = 0;
                            }//해당 배열 0으로 바꿔주기(합쳐줬으니깐)
                            index++;
                            j = z;
                            break;
                        }//같은 것 만남
                        else if (arr[i][z] != arr[i][j] && arr[i][z]!=0)
                        {
                            arr[i][index] = arr[i][j];
                            if (index != j) arr[i][j] = 0;
                            index++;
                            break;
                        }//다른 것 만남
                        else if (z == n - 1)
                        {
                            arr[i][index] = arr[i][j];
                            if (index != j) arr[i][j] = 0;
                            index++;//같은 것 안만나면 그대로 적재후 index++
                        }
                    }
                }
                else if (arr[i][j + 1] != 0)
                {
                    if (arr[i][j] == arr[i][j + 1])
                    {
                        arr[i][index] = 2 * arr[i][j];
                        if (index != j)
                        {
                            arr[i][j] = 0;
                            arr[i][j + 1] = 0;
                        }
                        else arr[i][j + 1] = 0;
                        index++;
                        j++;
                    }//뒤에것이랑 같음 
                    else
                    {
                        arr[i][index] = arr[i][j];
                        if (index != j) arr[i][j] = 0;
                        index++;//뒤에 것이랑 같지 않으면 그대로 적재 후 index++
                    }
                }
            }
        }
        index = 0;
    }
    //cout << "좌" << endl;
    //print(arr);
    //cout << endl;
}
void right()
{
    int index = n - 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = n - 1; j > -1; j--)
        {
            if (arr[i][j] != 0)
            {
                if (j == 0)
                {
                    arr[i][index] = arr[i][j];
                    if(index!=j) arr[i][j] = 0;
                    
                }//마지막
                else if (arr[i][j - 1] == 0)
                {
                    for (int z = j - 1; z > -1; z--)
                    {
                        if (arr[i][z] == arr[i][j])
                        {
                            arr[i][index] = 2 * arr[i][j];
                            if (index == j) arr[i][z] = 0;
                            else {
                                arr[i][z] = 0;
                                arr[i][j] = 0;
                            }//해당 배열 0으로 바꿔주기(합쳐줬으니깐)
                            index--;
                            j = z;
                            break;
                        }//같은 것 만남
                        else if (arr[i][z] != arr[i][j] && arr[i][z]!=0)
                        {
                            arr[i][index] = arr[i][j];
                            if (index != j) arr[i][j] = 0;
                            index--;
                            break;
                        }//다른 것 만남
                        else if (z == 0)
                        {
                            arr[i][index] = arr[i][j];
                            if (index != j) arr[i][j] = 0;
                            index--;//같은 것 안만나면 그대로 적재후 index++
                        }
                    }
                }//다음값 0 임
                else if (arr[i][j - 1] != 0)
                {
                    if (arr[i][j] == arr[i][j - 1])
                    {
                        arr[i][index] = 2 * arr[i][j];
                        if (index != j)
                        {
                            arr[i][j] = 0;
                            arr[i][j - 1] = 0;
                        }
                        else arr[i][j - 1] = 0;
                        index--;
                        j--;
                    }//뒤에것이랑 같음 
                    else
                    {
                        arr[i][index] = arr[i][j];
                        if (index != j) arr[i][j] = 0;
                        index--;//뒤에 것이랑 같지 않으면 그대로 적재 후 index++
                    }
                }
            }
        }
        index = n - 1;
    }
    //cout << "우" << endl;
    //print(arr);
    //cout << endl;
}
void copy(int to[21][21], int from[21][21])
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            to[i][j] = from[i][j];
}
void biggest(int arr[21][21])
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (arr[i][j] > maxx) maxx = arr[i][j];
}
void print(int arr[21][21])
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
}

어려운 점 및 개선점

DFS 순환 구조를 생각하는 것과 배열 옮기는 과정에서 index 적재하는 부분이 조금 까탈스러웠다. 모든 경우의 수를 꼼꼼히 생각하지 않아서 그런 것 같다. 앞으로 DFS 문제를 더 많이 풀어야 순환 구조도 금방 짤 수 있을 것 같다. 이번 달 안에 백준에 올라온 삼성 기출 문제 다 풀 것이다 !!!!!!!!!!!!!👊

'BOJ' 카테고리의 다른 글

[백준 14502] 연구소 (0)	2020.04.15
[백준 13460] 구슬탈출 2 (0)	2020.04.13
[백준 14500] 테트로미노 (0)	2020.03.29
[백준 14501] 퇴사 (0)	2020.03.24
[백준 17070] 파이프 옮기기 1 (0)	2020.02.16

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2025/05 »
일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

글 보관함

떠혀니의 노오력

티스토리 뷰