글 읽기 - 반례가 있을까요?

jkjan 3년 전 0

클릭해주셔서 감사합니다.

로직은 특별한 거 없습니다.

그냥 매 시도를 bfs 로 해서 탐색합니다.

근데 그 시도하는 과정이 좀 로직이 다를 순 있습니다.

위로 움직인다 그러면 4 x 4 보드에서

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

아래면

13 14 15 16

9 10 11 12

5 6 7 8

1 2 3 4

왼쪽이면

4 8 12 16

3 7 11 15

2 6 10 14

1 5 9 13

오른쪽은

13 9 5 1

14 10 6 2

15 11 7 3

16 12 8 4 순으로 수를 확인합니다.

그러니까 그 순서가 정수리를 위 아래 왼쪽 오른쪽으로 향하게 하고

정방향으로 탐색하는 거랑 같습니다.

아무튼 그렇게 탐색하면서 매 수 마다 위로 끝까지 올려보고

자기 자신과 같은 수를 발견하면, 원래 있던 곳을 0으로 바꾸고

그 수에다가 -2 를 곱해줍니다.

-2를 곱하는 이유는 그냥 2를 곱하면

그 밑에 줄에서 오는 애랑 수가 똑같아져서 또 더해질 수가 있기 때문입니다.

그런 일을 방지하기 위해 그 합체된 곳의 포인트를 따로 빼놨다가

움직임이 다 끝난 후 그 따로 뺴놓은 포인터들의 값에다가 다시 음수를 곱해줍니다.

위에 다른 수가 있다거나 맨 위에 도달했다면

그냥 자기 자신을 0으로 하고

그 공간에다가 원래 수를 채워넣어서 순간이동 시킵니다.

아마 이거 수 옮기는 건 다들 똑같이 구현하셨으리라고 봅니다.

여튼 움직이는 시도 하나를 하나의 노드로 보고

bfs 로 거리 재면서 탐색했습니다.

하나의 노드는 그때의 보드 상태, 거기까지 걸린 횟수를 포함합니다.

탐색하면서 항상 최대값을 갱신합니다.

정말 야박하게도 2% 올라가자마자 틀려버리네요...

#include <iostream>
#include <vector>
#include <queue>
#define MAX_SIZE 21
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
using namespace std;
typedef struct node {
    int board[MAX_SIZE][MAX_SIZE];
    int dist;
} node;
typedef struct pos {
    int y, x;
} pos;
typedef struct delta {
    pos start;
    pos deltaY, deltaX;
} delta;
int N;
delta policy[4];
void input(node* start);
int bfs(node start);

int main() {
    node start;
    input(&start);
    policy[UP] = {{2, 1}, {1, 0}, {0, 1}};
    policy[DOWN] = {{N-1, 1}, {-1, 0}, {0, 1}}; // DOWN
    policy[LEFT] = {{N, 2}, {0, 1}, {-1, 0}};
    policy[RIGHT] = {{1, N-1}, {0, -1}, {1, 0}};
    printf("%d", bfs(start));

    return 0;
}

void input(node* start) {
    scanf(" %d", &N);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            scanf(" %d", &(start->board[i][j]));
        }
    }
    start->dist = 0;
}

pos operator+(pos a, pos b) {
    return {a.y + b.y, a.x + b.x};
}

pos operator-(pos a, pos b) {
    return {a.y - b.y, a.x - b.x};
}

bool isValid(pos a) {
    return (1 <= a.y && a.y <= N) && (1 <= a.x && a.x <= N);
}

void move(int dir, int board[][MAX_SIZE]) {
    pos now = policy[dir].start;
    int cnt = 0;
    int* first;
    vector<int*> changed;
    int to;

    if (dir < 2) {
        first = &(now.x);
        to = policy[dir].start.x;
    }
    else {
        first = &(now.y);
        to = policy[dir].start.y;
    }

    while (true) {
        for (int i = 0; i < N; ++i) {
            cnt++;
            pos temp = now;

            if (board[now.y][now.x] != 0) {
                do {
                    temp = temp - policy[dir].deltaY;
                } while (isValid(temp) && (board[temp.y][temp.x] == 0));

                if (board[temp.y][temp.x] == board[now.y][now.x]) {
                    board[now.y][now.x] = 0;
                    board[temp.y][temp.x] *= -2;
                    changed.push_back(&(board[temp.y][temp.x]));
                }
                else {
                    temp = temp + policy[dir].deltaY;
                    int t = board[now.y][now.x];
                    board[now.y][now.x] = 0;
                    board[temp.y][temp.x] = t;
                }
            }
            now = now + policy[dir].deltaX;
        }
        if (cnt == (N * (N-1)) || N == 1)
            break;
        *first = to;
        now = now + policy[dir].deltaY;
    }
    for (auto c : changed) {
        *c *= -1;
    }
}

int getMax(int board[][MAX_SIZE]) {
    int maxBlock = -1;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            maxBlock = max(maxBlock, board[i][j]);
        }
    }
    return maxBlock;
}

// 디버깅 용
void printBlock(int board[][MAX_SIZE]) {
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            printf("%2d ", board[i][j]);
        }
        printf("\n");
    }
}

int bfs(node start) {
    queue<node> willVisit;
    willVisit.push(start);
    int ret = -1;
    while (!willVisit.empty()) {
        node nowVisit = willVisit.front();
        willVisit.pop();

        for (int i = UP; i <= RIGHT; i++) {
            node moved = nowVisit;
            moved.dist = nowVisit.dist + 1;
            if (moved.dist > 5)
                return ret;
            move(i, moved.board);

            int maxBlock = getMax(moved.board);
            ret = max(ret, maxBlock);
            willVisit.push(moved);
        }
    }
    return ret;
}

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