[SWEA 2382] 미생물 격리

문제  :[모의 SW 역량테스트] - 미생물 격리

[문제 출처] : SW Expert Academy [모의 SW 역량테스트] - 미생물 격리

 

 

[문제풀이]

 

이 문제 역시

차량 정비소 문제 : https://kbj96.tistory.com/12?category=904725 와 같이 시뮬레이션 문제이다!

1시간 마다 미생물 군집들이 이동 하게 되는데 이동하면서 여러 가지 주어진 조건들을 처리하고 나서

m 시간 후에 특정상황 : 미생물 총 수 를 구하는 문제이다

개인적으로 BOJ 문제에서 유사한 문제를 풀어보았기 때문에 풀이를 생각해내고 코드를 짜는데 있어서는

큰 어려움은 없었지만

[ 유사 문제 ] : https://www.acmicpc.net/problem/17143

 

각 테스트케이스마다 미생물의 양을 표시해두는 지도의 초기화 작업을 빼놓고 제출하니 tc 케이스 10개만 맞고 나머지는 계속 

틀려 몇 시간을 날린 문제이다 테스트케이스마다 n 값 (한 변의 셀의 개수) 이 다르기 때문에 필수적으로 해야 한다

 

+ 앞으로는 테스트케이스마다 초기화 작업을 잘 실행해 주어야 겠다 ㄲ

 

 

이 문제는 1시간 마다 각 군집들이(미생물) 이동 하게 된다 

이동 하고 나서는 크게 3가지의 경우를 맞닥뜨리게 된다

 

1. 빈칸에 어떠한 문제 없이 다음 칸으로 옮겨가는 경우

2. 약품이 칠해진 셀에 도착 (가장자리) 하는 경우

3. 미생물들이 한곳에 모이는 경우

 

여기서 조금은 까다로울 수 있는 부분이 3번인 경우이다. 

 

나는 이 부분을 처리하기 위해서 우선순위 큐를 활용하였다 

우선순위 큐를 활용해 미생물 수가 가장 많은 군집이 우선순위 큐의 TOP 을 유지(?) 하도록 해 

가장 미생물의 수가 많은 군집을 바로 사용 하여 처리 할 수 있다.  문제의 조건에서 "이동 방향은 군집들 중 미생물 수가 가장 많

은 군집의 이동방향이 된다. " 를 처리하기 위해서이다 

이는 우선순위 큐를 활용 하게 되면 아주 간단하게 처리가 가능 해진다.

 

 

다음과 같이 미생물 정보들을 구조체를 활용하여 "구조화" 를 시켰다

미생물들의 좌표와 생성자 및 미생물수가 가장 많은 군집이 TOP 을 유지하도록 하는 비교 함수  (연산자 오버라이딩을 통한) 

struct Node {
    int x, y;
    int amount, dir;
    Node(int x, int y, int a, int d) : x(x), y(y), amount(a), dir(d) {}
    bool operator < (const Node& tmp) const {
        return this->amount < tmp.amount;
    }
};

3번 부분을 중점적으로 어떻게 처리하면 되는지 예시 문제를 통하여 살펴보자

 

우선 순위 큐에서 top에 있는 노드를 활용 하면 이는 당연히 미생물의 수가 가장 많은것이 명백하다

 

1. 즉 미생물의 양 : 14를 보유한 군집이 우선순위 큐에서 꺼내어지게 된다

다음칸으로 이동하면 당연히 map[x][y]  == 0 인칸으로 이동 하게 된다. map[x][y] = 14 표시를 해주자.

 

2. 다음으로는 미생물의 양 : 8인 군집이 꺼내어 지게 되고 다음 칸으로 이동 할시 map[x][y]  (14) > 0 인

칸으로 이동 하게 된다 그냥 map[x][y] += 8 을 해주면 된다 그냥 미생물의 수만 더해주면 된다.

 

3. 다음으로는 미생물의 양 : 3 인 군집이 꺼내어지게 되고 마찬가지로 map[x][y] += 3 을 해주자!

 

여기서 설명을 안하고 넘어간 부분이 있다 표시를 해주고 나서 다시 우선순위 큐에 넣어 주면 되는가?

 

1번의 경우 우선순위 큐에 넣어 주어야 한다! 

왜냐 하면 1번의 군집이 미생물의 수가 가장 많으므로 합치고 난 후 그 군집의 이동 방향이 되기 때문이다

그렇다면 2번과 3번은 어떻게 해주어야 할까? 그냥 표시를 해주는 것으로 족하다 그 외의 정보는 쓸모없기 때문이다

다시! 우선순위 큐에 넣을 때는 새로운 우선순위 큐를 만들어서 넣어 주어야 한다 그렇지 않고 기존의 우선순위 큐에

넣게 되면 똑같은 것이 반복적으로 꺼내어져서 쓰여지게 될 것이기 때문이다

 

그 다음 새로운 우선순위 큐에서 꺼내어 검증 하는 작업을 수행 하여야 한다. 왜냐하면 1번을 넣었을 당시

미생물의 양은 : 14 이지만 합쳐진 결과로는 25 이기 때문이다 그렇기 때문에 map 에다가 표시를 해준 것이다

 

밑에 소스코드를 보면 쉽게 이해 할 수 있을 것이다

 

 

[소스 코드]

#include <iostream>
#include <cstring>
#include <queue>
#include <tuple>
using namespace std;
int n, m, k;
const int MAX = 100;
const int dx[] = { 0, -1, 1, 0, 0 };        // 상(1) 하(2) 좌(3) 우(4)
const int dy[] = { 0, 0, 0, -1, 1 };
int map[MAX][MAX];
struct Node {
    int x, y;
    int amount, dir;
    Node(int x, int y, int a, int d) : x(x), y(y), amount(a), dir(d) {}
    bool operator < (const Node& tmp) const {
        return this->amount < tmp.amount;
    }
};
priority_queue<Node> pq;
int reverseDir(int d) {
    if (d == 1) return 2;
    else if (d == 2) return 1;
    else if (d == 3) return 4;
    else return 3;
}
void init() {
    memset(map, 0, sizeof(map));
    for (int i = 0; i < n; i++) {
        map[i][n - 1] = map[n - 1][i] = map[0][i] = map[i][0] = -1;
    }
}
void db() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << map[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}
void solve() {
    priority_queue<Node> tpq;
    while (!pq.empty()) {
        int x, y, a, d;
        Node node = pq.top(); pq.pop();
        x = node.x, y = node.y, a = node.amount, d = node.dir;
        x += dx[d], y += dy[d];
        if (map[x][y] == 0) {
            map[x][y] = a;
            tpq.push(Node(x, y, a, d));
        }
        else if (map[x][y] == -1) {
            d = reverseDir(d), a /= 2;
            if (a == 0) continue;
            tpq.push(Node(x, y, a, d));
        }
        else map[x][y] += a;
    }
     db();
    while (!tpq.empty()) {
        int x, y, a, d;
        Node node = tpq.top(); tpq.pop();
        x = node.x, y = node.y, a = node.amount, d = node.dir;
        if (map[x][y] != -1 && map[x][y] != a) {
            a = map[x][y];
            pq.push(Node(x, y, a, d));
        }
        else pq.push(Node(x, y, a, d));
        if (map[x][y] != -1) map[x][y] = 0;
    }
     db();
}
int main(int argc, char** argv) {
    int test_case, T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> n >> m >> k;
        init();
        while (!pq.empty()) pq.pop();
        for (int i = 0; i < k; i++) {
            int x, y, am, dir;
            cin >> x >> y >> am >> dir;
            pq.push(Node(x, y, am, dir));
        }
        for (int hour = 1; hour <= m; ++hour) {
            solve();
        }
        int ans = 0;
        while (!pq.empty()) { ans += pq.top().amount, pq.pop(); }
        cout << "#" << test_case << " " << ans << "\n";
    }
    return 0;
}