[백준] 12100. 2048 (Easy)

문제

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

풀이

이게 왜 Easy인가.. 솔직히 어렵다기보다 자잘한 실수가 많기는 했는데 easy는 좀 아닌 것 같다. 문제에서 주의할 점은

부딪히면 그 턴에는 더 이상 합쳐지지 않는다는 것.
횟수가 5번까지라는 것.

이 두 조건 때문에 시간을 많이 잡아 먹었다. 기본적인 아이디어는 아래와 같이 잡았다.

1. 상, 하, 좌, 우로 움직일 수 있으며, 각 칸마다 연산을 한개씩 해준다.
2. 움직이고자 하는 방향의 다음 칸이 0이면, 그 칸으로 이동하고, 0이 아니면 이동을 끝낸다. 이 때, 각 칸을 계속 업데이트하지 않고, 모든 과정이 끝날 때 업데이트를 해준다. (코드에서 자세히 설명하겠다.)
3. 이동이 끝난 숫자는 다음과 같은 과정을 거친다.

다음 칸이 존재할 때, 현재 값과 같으면 합치고 이 숫자가 처음 시작했던 지점을 0으로 업데이트 해준다. 이 때, 다음 칸이 이미 합쳐진 적이 없다면, 합치지 않는다.
다음 칸이 존재하고 다음 칸과 현재 값이 같지 않으면 현재 위치를 현재 값으로 바꾸고 시작 지점을 0으로 업데이트 해준다.
다음 칸이 존재하지 않을 때, 현재 숫자가 이동을 했으면, 현재 칸에 현재 값을 넣어주고 시작 지점을 0으로 업데이트 해준다.
다음 칸이 존재하지 않을 때, 현재 숫자가 이동조차 못했다면, 그냥 그대로 둔다.

이해를 위해 그림을 보자.

case 1

그림 1

그림 2

그림 3

위의 그림에서 왼쪽으로 이동한다고 생각하자.

그림 1에서 맨 왼쪽의 2는 다음 칸이 존재하지 않고, 그 자리에서 움직이지 않았으므로, 그냥 냅둔다.

가장 오른쪽의 2는 0이 나올 때까지 움직여야하므로, 2번째 칸까지 이동 연산을 진행할 것이다. 그 후 다음 칸과 비교해서, 같으므로 합쳐져서 그림 3처럼 4가 될 것이다.

case 2

그림 4

그림 5

그림 6

case 1 처럼 4 + 4 = 8 로 만들고 맨 왼쪽으로 붙을 것이다. 맨 오른쪽 8은 일단 왼쪽으로 이동한다. 맨 왼쪽이 이미 충돌한 적이 있으므로 합쳐지지 않는다.

//

//  12100.cpp
//  BJ
//
//  Created by 신기열 on 20/10/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>

using namespace std;

int map[21][21];
int n, mxblock = 0, answer = 0;

int dir[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} };

// 이동 연산을 위한 함수
void calc(int i, int x, int y, int map[][21], int isCol[][21]){
    
    // 다음 칸을 체크하기 위한 변수
    int nx = x;
    int ny = y;
    
    // 함수는 한 칸만 연산을 하고, 밑의 DFS에서 for문을 돌려서 모든 칸에 대해 calc함수를 적용한다.
    while(1){
        // 다음 칸이 존재하며 & 다음 칸의 숫자가 0이면
        if(nx + dir[i][0] >= 1 && ny + dir[i][1] >= 1 && nx + dir[i][0] <= n && ny + dir[i][1] <= n && map[ny + dir[i][1]][nx + dir[i][0]] == 0){
            // 현재 탐색하는 칸을 다음 칸의 좌표로 이동해준다.
            nx = nx + dir[i][0]; ny = ny + dir[i][1];
        }
        // 더 이상 이동할 수 없으면 이동을 종료한다.
        else break;
    }
    
    // 여기까지 일단 "좌표"만 이동한 것이다. 따라서 배열은 아래에서 업데이트 해준다.
    
    // 이동 방향으로 쭉 움직이고 난 후의 좌표에서, 다음 칸이 존재하는 칸이면,
    if(nx + dir[i][0] >= 1 && ny + dir[i][1] >= 1 && nx + dir[i][0] <= n && ny + dir[i][1] <= n){
        // 만약 다음 칸이랑 현재 탐색 칸의 숫자가 같다면 & 다음 칸이 충돌한 적이 없으면
        if(map[ny + dir[i][1]][nx + dir[i][0]] == map[y][x] && isCol[ny + dir[i][1]][nx + dir[i][0]] == 0){
            // 다음 칸에 합쳐진 숫자를 업데이트해준다.
            map[ny + dir[i][1]][nx + dir[i][0]] = map[ny + dir[i][1]][nx + dir[i][0]] + map[y][x];
            // 이 칸은 충돌도 1로 업데이트 해준다.
            isCol[ny + dir[i][1]][nx + dir[i][0]] = 1;
            // 탐색 칸의 시작 지점은 이동한 후니까 0으로 업데이트 해준다.
            map[y][x] = 0;
        }
        
        // 다음 칸이 존재하긴 하는데 다음 칸과 숫자가 다를 때, 탐색 칸이 움직인 적이 없으면,
        else if(nx == x && ny == y){
            // 그냥 그대로 둔다.
            map[ny][nx] = map[y][x];
        }
        // 다음 칸과 숫자가 다르고 움직인 적은 있으면
        else{
            // 움직임이 끝난 최종 칸에 탐색 칸의 숫자를 업데이트 해주고, 시작 지점은 0으로 업데이트 해준다.
            map[ny][nx] = map[y][x];
            map[y][x] = 0;
        }
    }
    // 다음 칸이 없으면
    else{
        // 움직인 적이 없으면
        if(nx == x && ny == y){
            // 그냥 냅둔다.
            map[ny][nx] = map[y][x];
        }
        // 움직인 적은 있으면
        else{
            // 도착지점과 시작지점을 업데이트 해준다.
            map[ny][nx] = map[y][x];
            map[y][x] = 0;
        }
    }
}

void DFS(int map[21][21], int cnt, int mxblock){
    
    // 5번 탐색 했으면 더 이상 탐색을 해주지 않는다.
    if(cnt >= 5){ answer = max(mxblock, answer); return; }
    
    for(int i = 0; i < 4; i++){
        // 맵은 현재 상태에서 상, 하, 좌, 우로 움직일 수 있으므로 그걸 위한 맵이다.
        int tmpMap[21][21] = { 0, };
        // 충돌은 각 방향마다 계속 리셋해줘야한다. 어차피 한쪽 방향으로 이동했을 때 충돌 체크이므로 한 방향에서의 충돌만 체크해줘야한다. 이걸 리셋
        // 안하면 다른 방향으로 이동했을 때 리셋이 안되서 합쳐지지 않게 될 수도 있다.
        int isCol[21][21] = { 0, };
        // 임시맵을 초기화해준다.
        for(int p = 1; p <= n; p++){
            for(int q = 1; q <= n; q++){
                tmpMap[p][q] = map[p][q];
            }
        }
        // 밑으로 움직일 때
        if(i == 0){
            for(int y = n; y >= 1; y--){
                for(int x = 1; x <= n; x++){
                    calc(i, x, y, tmpMap, isCol);
                }
            }
        }
        // 위로 움직일 때
        else if(i == 1){
            for(int y = 1; y <= n; y++){
                for(int x = 1; x <= n; x++){
                    calc(i, x, y, tmpMap, isCol);
                }
            }
        }
        // 오른쪽으로 움직일 때
        if(i == 2){
            for(int y = 1; y <= n; y++){
                for(int x = n; x >= 1; x--){
                    calc(i, x, y, tmpMap, isCol);
                }
            }
        }
        // 왼쪽으로 움직일 때
        else if(i == 3){
            for(int y = 1; y <= n; y++){
                for(int x = 1; x <= n; x++){
                    calc(i, x, y, tmpMap, isCol);
                }
            }
        }
        // 각 방향으로 이동한 후 맵을 전부 탐색해서 가장 큰 블록의 숫자를 저장한다.
        for(int p = 1; p <= n; p++){
            for(int q = 1; q <= n; q++){
                mxblock = max(tmpMap[p][q], mxblock);
            }
        }
        
        // 최대 5번까지므로 dfs를 돌린다.
        DFS(tmpMap, cnt + 1, mxblock);
    
    }
}


int main(){
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> map[i][j];
        }
    }
    DFS(map, 0, 0);
    cout << answer;
    
    return 0;
}

Cat On The Keyboard

이 블로그 검색

[백준] 12100. 2048 (Easy)

댓글

댓글 쓰기