SWEA5648.md

원자 소멸 시뮬레이션

https://swexpertacademy.com/ [5648]

개요

원자들은 x, y(-1000<=x, y<=1000), d(상하좌우), e(에너지)의 고유한 값을 가지며 1초에 d방향으로 1칸 이동한다. 이렇게 이동하다 다른 원자와 부딪히면 에너지를 잃고 소멸된다. 소멸되는 에너지의 값을 구하는 문제

분석

두 가지 중요한 사실을 알아야 한다. 첫 번째는 첫 번째 주어진 좌표 값의 범위를 넘어가는 원자들은 소멸되지 않기 때문에 고려하지 않아도 된다는 점, 두 번째는 가장 끝과 끝에 위치한 원자 2개가 부딪히는 최대의 시간은 2000초라는 점이다.

본인의 알고리즘에서 map의 초기화에 관한 문제가 있었다. map을 초기화하면 시간초과가 나므로 원자를 이동할 때마다 map을 원래대로 해주었다. map 갱신 -> 원자 중복 여부 의 단계를 거치므로 2000초까지만 간다면 가장 끝에서 온 원자가 2000번의 map갱신을 하게 된다. 하지만 –1000~1000의 좌표의 개수가 2001개 이므로 2001번의 map갱신을 해주어야 오류가 나지 않는 것을 확인하였다.(이 문제 때문에 10시간 이상을 소모함)

알고리즘

1. 원자(x, y, d, e)를 이용하여 map에 체크

2. 원자를 이동시키며 맵의 원자 개수들을 갱신

3. 원자를 통하여 맵을 살피며 개수가 1초과인 원자들의 에너지를 sum에 더하고 제거(맵 초기화를 할 수 없으므로 제거할 때마다 맵을 갱신해주어야 한다.)

4. 개수가 1인 원자들은 다시 저장.

5. 2~4를 4001번 반복.

소스

#include <stdio.h>
 
int won[1010][4], map[4001][4001][2], bang[4][2] = { {-1,0}, {1,0},{0,-1}, {0,1} };
 
int bc(int x, int y)
{
    if (x >= 0 && x <= 4000 && y >= 0 && y <= 4000) return 1;
    return 0;
}
 
int main()
{
    int T, i, j, k, l, n, tt, sn, x, y, nx, ny, d, sum;
    scanf("%d", &T);
    for (i = 1; i <= T; i++)
    {
        scanf("%d", &n);
        sum = 0;
 
        for (j = 1; j <= n; j++)
        {
            for (k = 0; k < 4; k++) scanf("%d", &won[j][k]);
            tt = won[j][0];
            won[j][0] = ((won[j][1] * -1) + 1000) * 2;
            won[j][1] = (tt + 1000) * 2;
            won[j][4] = 0;
            map[won[j][0]][won[j][1]][0]++;
        }
 
        sn = n;
        for (j = 0; j <= 4000; j++)
        {
            if (sn == 0) break;
            n = sn;
            sn = 0;
            for (k = 1; k <= n; k++)
            {
                x = won[k][0];
                y = won[k][1];
                d = won[k][2];
                if (bc(x, y) == 1) map[x][y][0]--;
                nx = x + bang[d][0];
                ny = y + bang[d][1];
                if (bc(nx, ny) == 1) map[nx][ny][0]++;
            }
            for (k = 1; k <= n; k++)
            {
                nx = won[k][0] + bang[won[k][2]][0];
                ny = won[k][1] + bang[won[k][2]][1];
                if (bc(nx, ny) == 1)
                {
                    if (map[nx][ny][0] > 1)
                    {
                        map[nx][ny][0]--;
                        if (map[nx][ny][1] == 0) map[nx][ny][1] = 1;
                        sum += won[k][3];
                    }
                    else if (map[nx][ny][0] == 1 && map[nx][ny][1] == 1)
                    {
                        map[nx][ny][0] = 0;
                        map[nx][ny][1] = 0;
                        sum += won[k][3];
                    }
                    else
                    {
                        sn++;
                        won[sn][0] = nx;
                        won[sn][1] = ny;
                        for (l = 2; l < 4; l++) won[sn][l] = won[k][l];
                    }
                }
            }
        }
        printf("#%d %d\n", i, sum);
    }
}