습격자 초라기

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

1006번: 습격자 초라기

 

문제에서 주어진 원 공간은 인접한 방의 개수가 항상 3개이다.

인접한 방은 항상 방의 숫자가 똑같으므로 인접한 방을 접근할 수 있는 자료구조를 만들고

데이터를 넣은 다음에 입력값(N)을 넘지않는 인접 방의 개수를 구하도록 저장했다.

자신의 인접한 방 중에 조건에 만족하는 방의 개수가 가장 적은 방부터 접근하여 풀어봤는데

결과는 실패이다.

using namespace std;
 
typedef struct{
    int value;
    int near[3];
    int num;
} NODE;
struct NODE_COMP
{
    bool operator()(const NODE& user1, const NODE& user2)
    {
        return user1.num < user2.num;
    }
};
int MAP[20001];
bool USE[20001];
vector ORDER;
int N, W, NUM;
void order(int index)
{
    int left, right, updown;
    if (index <= N)
    {
        left = (index - 1 < 1) ? N : index - 1;
        right = (index + 1 > N) ? 1 : index + 1;
        updown = index + N;
    }
    else
    {
        left = (index - 1 <= N) ? 2*N : index - 1;
        right = (index + 1 > 2*N)? N+1 : index + 1;
        updown = index - N;
    }
 
    if (MAP[index] + MAP[left] <= W)
        ORDER[index - 1].near[ORDER[index - 1].num++] = left;
    if (MAP[index] + MAP[right] <= W)
        ORDER[index - 1].near[ORDER[index - 1].num++] = right;
    if (MAP[index] + MAP[updown] <= W)
        ORDER[index - 1].near[ORDER[index - 1].num++] = updown;
}
int set(NODE nnn)
{
    int src = nnn.value;
    if (USE[src] == 0)
    {
        USE[src] = 1;
        if(nnn.num == 0)
            return 0;
        else
        {
            for (int i = 0; i < nnn.num;i++)
                if(USE[nnn.near[i]] == 0)
                {
                    USE[nnn.near[i]] = 1;
                    return 1;
                }
            return 0;
        }
    }
    return 0;
}
int main()
{
    int T;
    for (scanf("%d", &T); T > 0; T--)
    {
        memset(&MAP, 0, sizeof(MAP));
        memset(&USE, 0, sizeof(USE));
        NUM = 0;
        scanf("%d %d", &N, &W);
        ORDER.clear();
        for (int i = 1; i <= N * 2; i++)
        {
            NODE temp; temp.num = 0; temp.value = i;
            ORDER.push_back(temp);
        }
 
        for (int i = 1; i <= N; i++)
            scanf("%d", &MAP[i]);
        for (int i = 1; i <= N; i++)
            scanf("%d", &MAP[i+N]);
 
        for (int i = 1; i <= 2 * N;i++)
            order(i);
 
        sort(ORDER.begin(), ORDER.end(), NODE_COMP());
        int A = 2*N;
        for (int i = 0; i < N * 2; i++)
                A -= set(ORDER[i]);
         
        printf("%d\n", A);
    }
    return 0;
}