SWEA2382.md

미생물 격리

https://swexpertacademy.com/main/main.do [2382] 미생물 격리

개요

좌표(x, y)와 방향(dir)과 가중치(count)가 주어진 미생물들(x, y, count, dir)이 1시간에 1칸씩 dir방향으로 이동한다. 이동하다 만나면 count가 합쳐지는데 가장 높은 count를 가진 미생물의 dir이 합쳐진 미생물의 dir가 된다. Map의 끝(0행, 0열, N행, N열)에서는 count가 반으로 줄고 dir이 반대로 바뀐다. Map의 크기는 N*N(N<=100)이고 시간은 M<=1000, 미생물의 수 K<=1000 이다.

분석

시간 복잡도

시간마다 미생물들이 이동하므로 살아있는 미생물들의 수 * 시간 = 1000 * 1000이 된다.

공간 복잡도

Map의 크기인 100*100*4 byte이다.

알고리즘

1. Map초기화

2. K개의 미생물을 이동(Mi[i].x+bang[dir].x, Mi[i].y+bang[dir].y)시키며 Map[Mi[i].x][Mi[i].y]의 max(해당 좌표의 최대count)를 갱신하고 sum에 count를 더해준다.

3. K개의 미생물을 살펴보며 Map[Mi[i].x][Mi[i].y]의 max 값이 있을 경우에 max값과 다른 count를 갖는 Mi[i]를 제거한다. 또한 조건2도 동시에 체크해주며 갱신할 수 있다. (살릴 미생물에만 Mi[++ct]=Mi[i]의 방법을 쓰면 간단하게 제거할 수 있다. 최종적으로 ct값이 새로운 미생물 개수가 된다.)

4. 1~3을 M번 반복한다.

5. K개의 미생물의 count를 다 더한다.

기타

미생물들을 시간에 따라 움직이는 것 이외의 방법은 없다. 따라서 조건1(미생물들의 합쳐짐)과 조건2(Map의 끝)를 검사하며 1시간씩 시뮬레이션을 하여야한다. 미생물변수만으로 이동 시 K^2(백만)의 시간복잡도로 조건1을 검사할 수 있다.(1번 미생물과 K개의 미생물의 좌표가 같은 지 검사) 이차원배열 Map을 추가로 사용한다면 N^2(만)의 시간복잡도로 조건1을 검사(N^2은 배열 초기화, 검사 자체는 K(천)의 시간복잡도)할 수 있다.

주의할 점은 Map에 해당좌표의 미생물들의 count의 총합만을 저장 시 가장 큰 count를 찾을 수 없다. 추가적으로 max(최대count)값을 저장해주어야 가장 큰 count를 찾을 수 있다. 합쳐지는 미생물의 count가 같을 수는 없다고 하였으므로 이동 시에 Map에 count의 최대값을 저장한 후에 다시 K번 만큼 돌며 최댓값과 다른 count를 갖는 미생물들을 제거한다.

소스

#include <stdio.h>
 
int bang[5][2] = { {0,0}, {-1,0},{1,0},{0,-1},{0,1} };
int map[110][110][4];//최대 미생물 수랑 번호와 군집 수와 미생물 수
int sega[1010][5];
 
int bc(int r, int c, int n)
{
    if (r == 0 || c == 0 || r == n - 1 || c == n - 1) return 1;
    return 0;
}
int move(int k, int n)
{
    int i, j,l, ct=0, nx, ny;
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= n; j++)
        {
            for (l = 0; l < 4; l++)
            {
                map[i][j][l] = 0;
            }
        }
    }
    for (i = 1; i <= k; i++)
    {
        sega[i][0] += bang[sega[i][3]][0];
        sega[i][1] += bang[sega[i][3]][1];
        map[sega[i][0]][sega[i][1]][2]++;
        if (map[sega[i][0]][sega[i][1]][0] <= sega[i][2])
        {
            map[sega[i][0]][sega[i][1]][0] = sega[i][2];
            map[sega[i][0]][sega[i][1]][1] = i;
        }
        map[sega[i][0]][sega[i][1]][3] += sega[i][2];
    }
    for (i = 1; i <= k; i++)
    {
        nx = sega[i][0];
        ny = sega[i][1];
        if (map[nx][ny][1] != i) sega[i][4] = 1;
        else sega[i][2] = map[sega[i][0]][sega[i][1]][3];
    }
    for (i = 1; i <= k; i++)
    {
        if (bc(sega[i][0], sega[i][1], n) == 1)
        {
            if (sega[i][3] == 1) sega[i][3] = 2;
            else if (sega[i][3] == 2) sega[i][3] = 1;
            else if (sega[i][3] == 3) sega[i][3] = 4;
            else if (sega[i][3] == 4) sega[i][3] = 3;
 
            sega[i][2] /= 2;
            if (sega[i][2] == 0) sega[i][4] = 1;
        }
    }
    for (i = 1; i <= k; i++)
    {
        if (sega[i][4]==0)
        {
            ++ct;
            for (j = 0; j <=1; j++) sega[ct][j] = sega[i][j];
            sega[ct][3] = sega[i][3];
            sega[ct][2] = sega[i][2];
            sega[ct][4] = 0;
        }
    }
    return ct;
}
 
 
int main()
{
    int T, N, M, K, i, j, l, sum;
    scanf("%d", &T);
    for (i = 1; i <= T; i++)
    {
        sum = 0;
        for (j = 0; j < 100; j++)
        {
            for (l = 0; l < 100; l++)
            {
                map[i][l][0] = 0;
                map[i][l][1] = 0;
                map[i][l][2] = 0;
                map[i][l][3] = 0;
            }
        }
        for (j = 0; j < 1010; j++)
        {
            for (l = 0; l < 5; l++) sega[j][l] = 0;
        }
        scanf("%d%d%d", &N, &M, &K);
        for (j = 1; j <= K; j++)
        {
            scanf("%d%d%d%d", &sega[j][0], &sega[j][1], &sega[j][2], &sega[j][3]);
            map[sega[j][0]][sega[j][1]][0] = sega[j][2];
            map[sega[j][0]][sega[j][1]][1] = sega[j][3];
            map[sega[j][0]][sega[j][1]][2]++;
        }
         
        for (j = 1; j <= M; j++)
        {
            K=move(K, N);
        }
        for (j = 1; j <= K; j++) sum += sega[j][2];
        printf("#%d %d\n", i, sum);
    }
}