글 읽기 - 12100번 2048(Easy) 문제 어는 부분이 잘못 된 건지 모르겠습니다.

95kim1 3년 전 0

코드는 dfs 방식으로 짰고 (maxBlock이 dfs 함수입니다.) 보드에서 블록들이 상하좌우로 이동하는 코드는 tiltBoard함수입니다. tiltBoard에서 블록이 이동하는 코드는 예를 들어 블록들이 위로 향할 때 보드의 한 컬럼의 블록들을 순서대로 위로 밀어 넣는 방식을 썼습니다. (아래 좌 우 방향도 같은 방식)

게시판의 여러 테스트 케이스들을 넣어봐도 다 맞는 값이 나오는데 채점을 하면 틀렸다고 나옵니다. 하루종일 테스트케이스를 돌려보고 뭐가 틀렸는지 봤는데 도저히 모르겠습니다. 반례나 코드의 오타 혹은 논리적으로 틀린부분을 알려주실 수 있을까요? ㅠㅠ

(블록들을 이동할 때 큐를 쓰면 편하다는 것을 알았고 문제 자체는 통과를 했습니다. 그럼에도 큐를 쓰지 않고 반복문으로 이동시킨 이 코드가 왜 틀렸는지를 알고 싶어서 질문드려봅니다...)

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

#define maxN 20
stack<int> s;
int N, board[maxN][maxN] = { 0, }, maxNum = 0;

void copyArr(int from[][maxN], int to[][maxN]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            to[i][j] = from[i][j];
        }
    }
}

void tiltBoard(int i) {
    int visit[maxN][maxN] = { 0, };
    switch (i) {
    case 0: //위로 기울이기
        for (int j = 0; j < N; j++) {
            for (int i = 1; i < N; i++) {          
                if (board[i][j] == 0) continue;
                int itemp = i - 1;
                //이동할 타일의 최종 위치 찾기(보드의 빈공간 제치기)
                while (itemp >= 0 && board[itemp][j] == 0) {
                    itemp--;
                }
                //타일에 막히고, 막은 타일이 같은 수이고, 아직 막은 타일이 합친적 없는 타일일 때
                if (itemp >= 0 && board[itemp][j] == board[i][j] && visit[itemp][j] == 0) {
                    visit[itemp][j] = 1;
                    board[itemp][j] += board[i][j];
                    board[i][j] = 0;
                }//나머지 (벽에 막히거나, 다른 수거나, 이미 합쳐진 타일일 때 (단, 그대로인 경우 제외))
                else if (itemp + 1 != i) {
                    board[itemp + 1][j] = board[i][j];
                    board[i][j] = 0;
                }
            }
        }
        break;
    case 1: //아래로
        for (int j = 0; j < N; j++) {
            for (int i = N - 2; i >= 0; i--) {
                if (board[i][j] == 0) continue;
                int itemp = i + 1;
                while (itemp <= N - 1 && board[itemp][j] == 0) {
                    itemp++;
                }
                if (itemp < N && board[itemp][j] == board[i][j] && visit[itemp][j] == 0) {
                    visit[itemp][j] = 1;
                    board[itemp][j] += board[i][j];
                    board[i][j] = 0;
                }
                else if (itemp - 1 != i) {
                    board[itemp - 1][j] = board[i][j];
                    board[i][j] = 0;
                }
            }
        }
        break;
    case 2: //왼쪽으로
        for (int i = 0; i < N; i++) {
            for (int j = 1; j < N; j++) {
                if (board[i][j] == 0) continue;
                int jtemp = j - 1;
                while (jtemp >= 0 && board[i][jtemp] == 0) {
                    jtemp--;
                }
                if (jtemp >= 0 && board[i][jtemp] == board[i][j] && visit[i][jtemp] == 0) {
                    visit[i][jtemp] = 1;
                    board[i][jtemp] += board[i][j];
                    board[i][j] = 0;
                }
                else if (jtemp + 1 != j) {
                    board[i][jtemp + 1] = board[i][j];
                    board[i][j] = 0;
                }
            }
        }
        break;
    case 3: //오른쪽으로
        for (int i = 0; i < N; i++) {
            for (int j = N - 2; j >= 0; j--) {
                if (board[i][j] == 0) continue;
                int jtemp = j + 1;
                while (jtemp < N && board[i][jtemp] == 0) {
                    jtemp++;
                }
                if (jtemp >= 0 && board[i][jtemp] == board[i][j] && visit[i][jtemp] == 0) {
                    visit[i][jtemp] = 1;
                    board[i][jtemp] += board[i][j];
                    board[i][j] = 0;
                }
                else if (jtemp - 1 != j) {
                    board[i][jtemp - 1] = board[i][j];
                    board[i][j] = 0;
                }
            }
        }
        break;
    }
}

void maxBlock(int n) {
    int temp[maxN][maxN];
    if (n == 5) {
        int cur = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cur = (cur < board[i][j]) ? board[i][j] : cur;
            }
        }
        //테스트용
        /*if (maxNum < cur) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    printf("%6d", board[i][j]);
                }
                printf("\n");
            }
            printf("\n");
            maxNum = cur;
        }*/
        maxNum = (maxNum < cur) ? cur : maxNum;
        return;
    }
    
    copyArr(board, temp);
    for (int i = 0; i < 4; i++) { 
        tiltBoard(i);
        maxBlock(n + 1);
        copyArr(temp, board);
    }
}

int main(void) {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cin >> board[i][j];
    }
    maxBlock(0);
    printf("%d\n", maxNum);
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

12100번 2048(Easy) 문제 어는 부분이 잘못 된 건지 모르겠습니다.

95kim1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말