5648. 원자 소멸 시뮬레이션

5648. 원자 소멸 시뮬레이션

최악의 경우를 떠올려봐도...시간통과될 것 같은데 왜 안되는것인지 모르겠다...ㅠㅠ

SW EXPERT 에 질문을 올렸더니, 한분께서 STL QUEUE 가 속도가 느린것 같다고, 배열로 만들어서 해보면 통과라고 했는데 정말 됐다.

어떠한 이유인지 정확히 모르겠으나, STL 의 QUEUE가 삽입,삭제 연산이나 이런부분에서 속도가 좀 저하되는 것 같다. 

이 문제는 푸는 과정에서 시간초과가 정말 많이 났다.

맨 처음에는 생각했던 방식은

 1. 모든 점들을 이동 → 2. 겹쳐지는 점들을 다시 탐색 → 3. 겹친점들 제거 → 4. 맵 초기화 방식 으로 순서적으로 진행하였다.

하지만 시간초과 해결을 못해서 이리저리 낑낑대고 인터넷으로 다른 분들 보면서 최적의 정답 코드로 수정했다.

그러나 처음 정답 코드도 큐를 배열로 짰더니 통과하였다.

최종 정답 코드 에서는 맨 처음에 했던 방식의 점들을 이동하고 겹쳐지는 점들을 탐색하고 제거하는 과정을 하나로 만들어냈다.

원자들의 값을 하나의 셀에 축적시키고 나중에 돌아왔을 때 해결하는 방식이었다. 이때 아이디어는 축적된 에너지 값이, 내가 가지고 있는 에

너지값보다 크면 셀이 축적되었다 라는 아이디어였다. 그 아이디어를 통해서 위의 과정을 통합하면서 코드가 좀 통합된 느낌...?

<최종 정답 코드>

#include<iostream>
 
 
#define MAXSIZE 1000
#define ADD 1000
#define MAX 4001
using namespace std;
 
 
typedef struct atom {
    int x;
    int y;
    int dir;
    int energy;
}atom;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
int map[MAX][MAX];
 
atom q[MAXSIZE];
int front;
int rear;
int qsize;
bool empty()
{
    if (front==rear)
        return true;
    else
        return false;
}
 
bool full()
{
    if ((rear+1)%MAXSIZE == front)
        return true;
    else
        return false;
}
void push(atom tmp)
{
    if (full())
        return;
 
    qsize++;
    q[rear] = tmp;    
    rear = (rear + 1) % MAXSIZE;
 
}
 
atom pop()
{
    atom ret = { 0,0,0,0 };
 
    if (empty())
        return ret;
 
    qsize--;
    ret = q[front];
    front = (front + 1) % MAXSIZE;
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int N, ans = 0;
        cin >> N;
 
        for (int i = 0; i < N; i++)
        {
            int x, y, d, e;
            cin >> y >> x >> d >> e;
            x += ADD;
            y += ADD;
            x *= 2;
            y *= 2;
            map[x][y] = e;
 
            atom tmp = { x,y,d,e };
            push(tmp);
        }
 
        while (!empty())
        {
            // 원자 이동하기
            int size = qsize;
            for (int i = 0; i < size; i++)
            {
                atom now = pop();
                
                int x = now.x;
                int y = now.y;
                int d = now.dir;
                int e = now.energy;
                int nx = x + dx[d];
                int ny = y + dy[d];
 
                atom moved = { nx,ny,d,e };
 
 
                // 현재 지점이 원자가 충돌된 지점일 때
                if (now.energy < map[x][y])
                {
                    ans += map[x][y];
                    map[x][y] = 0;
                    continue;
                }
                // 이동할 곳의 범위 체크
                if (nx >= 0 && ny >= 0 && nx < MAX && ny < MAX)
                {
                    // 이동할 곳에 원자가 있을 때
                    if (map[nx][ny] != 0)
                        map[nx][ny] += e;
 
                    // 이동할 곳에 원자가 없을 때
                    else
                    {
                        map[nx][ny] = e;
                        push(moved);
                    }
                }
                // 원자 삭제
                map[x][y] = 0;
            }
        }
 
        cout << "#" << t << " " << ans << endl;
    }
 
    return 0;
}
 

<정답 코드 - 맨 처음에 풀었던 방법 >

#include<iostream>
#include<vector>
 
#define MAXSIZE 1000
#define ADD 1000
#define MAX 4001
using namespace std;
 
 
typedef struct atom {
    int x;
    int y;
    int dir;
    int energy;
}atom;
 
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
int map[MAX][MAX];
 
atom q[MAXSIZE];
int front;
int rear;
int qsize;
 
bool empty()
{
    if (front==rear)
        return true;
    else
        return false;
}
 
bool full()
{
    if ((rear+1)%MAXSIZE == front)
        return true;
    else
        return false;
}
void push(atom tmp)
{
    if (full())
        return;
 
    qsize++;
    q[rear] = tmp;    
    rear = (rear + 1) % MAXSIZE;
 
}
 
atom pop()
{
    atom ret = { 0,0,0,0 };
 
    if (empty())
        return ret;
 
    qsize--;
    ret = q[front];
    front = (front + 1) % MAXSIZE;
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int N, ans = 0;
        cin >> N;
 
        for (int i = 0; i < N; i++)
        {
            int x, y;
            atom tmp;
            cin >> y >> x >> tmp.dir >> tmp.energy;
            tmp.x = x + ADD;
            tmp.x *= 2;
            tmp.y = y + ADD;
            tmp.y *= 2;
            map[tmp.x][tmp.y]++;
    
            push(tmp);
        }
 
        while (!empty())
        {
            // 점들 이동하기
            int size = qsize;
            for (int i = 0; i < size; i++)
            {
                atom cur = pop();
                
                int x =cur.x;
                int y = cur.y;
                int dir = cur.dir;
                int energy = cur.energy;
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                
                atom moved = { nx,ny,dir,energy };
 
                map[x][y]--;
                // 범위 벗어나면 제외
                if (nx >= 0 && ny >= 0 && nx < MAX && ny < MAX)
                {
                    map[nx][ny]++;
                    push(moved);
                }
            }
 
            // 겹치는 곳들 삭제
            vector<pair<int, int>> temp;
            size = qsize;
            for (int i = 0; i < size; i++)
            {
                atom cur = pop();
 
                int x = cur.x;
                int y = cur.y;
                int dir = cur.dir;
                int energy = cur.energy;
                int nx = x + dx[dir];
                int ny = y + dy[dir];
 
                atom moved = { nx,ny,dir,energy };
 
                if (map[x][y] > 1)
                {
                    ans += energy;
                    temp.push_back({ x,y });
                }
                else
                    push(cur);
            }
 
            // 맵 초기화
 
            for (int i = 0; i < temp.size(); i++)
            {
                map[temp[i].first][temp[i].second] = 0;
            }
        }
        cout << "#" << t << " " << ans << endl;
    }
 
    return 0;
}
 

<시간 초과 코드>

#include<iostream>
#include<queue>
 
#define ADD 1000
#define MAX 4001
using namespace std;
typedef struct atom {
    int x;
    int y;
    int dir;
    int energy;
}atom;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
int map[MAX][MAX];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int N, ans = 0;
        cin >> N;
 
        queue<atom> q;
 
        for (int i = 0; i < N; i++)
        {
            int x, y, d, e;
            cin >> y >> x >> d >> e;
            x += ADD;
            y += ADD;
            x *= 2;
            y *= 2;
            map[x][y] = e;
 
            atom tmp = { x,y,d,e };
            q.push(tmp);
        }
 
        while (!q.empty())
        {
            // 원자 이동하기
            int size = q.size();
            for (int i = 0; i < size; i++)
            {
                int x = q.front().x;
                int y = q.front().y;
                int d = q.front().dir;
                int e = q.front().energy;
 
                int nx = x + dx[d];
                int ny = y + dy[d];
 
                atom now = { x,y,d,e };
                atom moved = { nx,ny,d,e };
 
                q.pop();
 
                // 현재 지점이 원자가 충돌된 지점일 때
                if (now.energy < map[x][y])
                {
                    ans += map[x][y];
                    map[x][y] = 0;
                    continue;
                }
                // 이동할 곳의 범위 체크
                if (nx >= 0 && ny >= 0 && nx < MAX && ny < MAX)
                {
                    // 이동할 곳에 원자가 있을 때
                    if (map[nx][ny] != 0)
                        map[nx][ny] += e;
 
                    // 이동할 곳에 원자가 없을 때
                    else
                    {
                        map[nx][ny] = e;
                        q.push(moved);
                    }
                }
                // 원자 삭제
                map[x][y] = 0;
            }
        }
 
        cout << "#" << t << " " << ans << endl;
    }
 
    return 0;
}