[SWEA] 2382. 미생물 격리

문제 이해

시뮬레이션 문제이다.

시간의 흐름에 따라 어떻게 움직이는지, 예외 상황 파악 등이 중요한 문제였다. 

 

일단 군집 배열을 둔다. (군집의 위치, 미생물 수, 방향 등을 저장하는 배열이다.)

군집은 최대 1000개이고, 시간은 최대 1000이니까, 각 시간 별로 군집에 대한 처리를 하면 1000*1000 이라 시간 내에 들어온다. 그래서 그냥 루프를 돌리면 되겠다고 생각했다. 

 

루프를 돌면서 할 것은,

1. 위치를 옮겨준다.

2. 만약 약품이 있는 위치이면 미생물 수를 반으로 감소시키고, 방향을 바꿔준다.

3. 만약에 해당 위치에 여러 군집이 모이면, 그 중 가장 큰 군집으로 모아버리고 나머지 군집은 소멸되었다 생각한다.

 

Trouble shooting:

처음에는 군집마다 저 세 단계를 처리하는 식으로 구현했다.

근데 그렇게 하면 3번을 할 때 문제가 발생했다.

만약에 A 군집이 300마리, B 군집이 200 마리, C 군집이 400 마리 있었다고 하면

A를 일단 위치시키고 B가 이곳에 왔을 때 A보다 큰지 작은지를 판단한다. A가 더 크니까 A에 병합한다. 

그 후에 C가 이곳에 오면 A의 크기가 500 이고 C가 400 이라 A에 병합된다. 근데 이러면 안된다!!

C가 제일 컸으니까 C에 A와 B 군집이 병합되어야 한다.

 

결국 이 병합이란 걸 하나하나 처리할 것이 아니라, 다 이동시킨 다음에 비교해봐야 한다는 것이다.

 

Final Solution

그래서 루프를 두 개를 돌리는 방향으로 다시 잡았다. 어차피 시간 복잡도는 큰 차이가 없으니까 (1000*2000)

매 시간마다

1. 1번 루프에서는 위치를 옮겨주고, 약품 처리를 한다.
2. 군집 배열 정렬
3. 2번 루프에서는 중복되는 좌표들에 대해서 가장 큰 군집에 몰빵하기를 처리한다. 

1번과 2번 루프 사이에 좌표 기준으로 정렬하여 같은 좌표에 있는 애들이 배열에 몰려있도록 했다. 그럼 순차 탐색을 하면서 중복 처리를 할 수 있기 때문이다. 

 

이미 소멸한 군집은 num = 0 으로 처리해서 이런 경우 다 continue로 탐색 안하도록 했다. 

 

작성 코드

#include <stdio.h>
 // 입력 변수
int N, M, K; // 셀의 개수, 격리 시간, 미생물 군집 개수
typedef struct group {
    int y;
    int x;
    int num;
    int dir;
}GROUP;
GROUP G[1000 + 10]; // 군집 배열

// 방향 벡터
int dy[] = { 0, -1, 1, 0, 0 }; // 상, 하, 좌, 우
int dx[] = { 0, 0, 0, -1, 1 }; // 상, 하, 좌, 우

int getAns(void) {
    // 미생물 배열을 돌면서 남은 미생물 수 센다
    int ret = 0;
    for (int i = 1; i <= K; i++) {
        ret += G[i].num;
    }
    return ret;
}

int getInput(void) {
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 1; i <= K; i++) {
        scanf("%d %d %d %d", &G[i].y, &G[i].x, &G[i].num, &G[i].dir);
    }
}

int changeDir(int dir) {
    switch (dir) {
    case 1: 
        dir = 2;
        break;
    case 2:
        dir = 1;
        break;
    case 3:
        dir = 4;
        break;
    case 4:
        dir = 3;
        break;       
    }
    return dir;
}


int comp(const void* a, const void* b) {
    GROUP* p = (GROUP*)a;
    GROUP* q = (GROUP*)b;
    if (p->y == q->y) return p->x - q->x;
    else return p->y - q->y;
}

void move(int time) {
    for (int i = 1; i <= K; i++) {
        // 움직이고
        if (G[i].num == 0) continue;
        G[i].y += dy[G[i].dir];
        G[i].x += dx[G[i].dir];
        // 만약 약품 위치이면 방향과 개체 수 바꾸고
        if (G[i].y == 0 || G[i].x == 0 || G[i].y == N - 1 || G[i].x == N - 1) {
            G[i].num = G[i].num / 2;
            G[i].dir = changeDir(G[i].dir);
        }
    }

    qsort(G, K+1, sizeof(G[0]), comp); // 좌표 기준 정렬 -> 같은 애들은 붙어 있을 것

    int s, max_i; // 해당 좌표의 시작점, 해당 좌표 중 최대 num 가진 좌표
    for (int i = 1; i <= K; i++) {
        if (G[i].num == 0) continue;
        s = i;
        max_i = i;
        while(G[i].y == G[i + 1].y && G[i].x == G[i + 1].x) {
            // 다음 거랑 동일
            i++;
            if (G[i].num > G[max_i].num) max_i = i;
        }
        for (int j = s; j <= i; j++) {
            // max_i 로 다 합치기
            if (j == max_i) continue;
            if (G[j].num == 0) continue;
            G[max_i].num += G[j].num;
            G[j].num = 0; 
        }
    }
}


int main(void) {

    freopen("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        // 각 테스트 케이스
        // 1. 초기화
        for (int i = 0; i < K; i++) {
            G[i].y = 0;
            G[i].x = 0;
            G[i].dir = 0;
            G[i].num = 0;
        }
        // 2. 입력받기
        getInput();
        // 3. 풀이
        for (int m = 1; m <= M; m++) {
            move(m);
        }
        // 4. 출력
        printf("#%d %d\n", t + 1, getAns());
    }
    return 0;
}