[소프트웨어 익스퍼트 아카데미][SWEA][모의 SW 역량테스트][ C++][2382번] 미생물 격리

요즘 바빠서 티스토리 관리를 못해 오랫만에 올립니다. 이제 바빠도 주말에 한문제 씩은 풀어서 올리도록 하겠습니다.

 

이문제는 bfs를 이용해서 하나하나의 미생물을 이동시키는 방법으로 접근하여 해결하였습니다.

 

#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;
struct q_info {
    int x;
    int y;
    int d;
    int s;
};
struct {
    int size;
    int max_size;
    int d;
}map[101][101];
 
int N, M, K, ans;
queue<q_info> q;
int p_x[4] = { 0,0,-1,1 };
int p_y[4] = { -1,1,0,0 };
 
void bfs() {
    for (int i = 0; i < M; i++) {
        //print();
        memset(map, 0, sizeof(map));
        while (!q.empty()) {
            q_info cur = q.front();
            q.pop();
            int nx = cur.x + p_x[cur.d - 1];
            int ny = cur.y + p_y[cur.d - 1];
            if (nx > -1 && nx < N && ny>-1 && ny < N) { //범위안 이라면 
                if (nx == 0 || nx == N - 1 || ny == 0 || ny == N - 1) { //양 끝이라면
                    if ((cur.s / 2) == 0) continue;
                    map[ny][nx].size += (cur.s / 2);
                    if (map[ny][nx].max_size < (cur.s / 2)) { //max 값이 바뀐다면
                        map[ny][nx].max_size = (cur.s / 2);
                        int next;
                        if (cur.d == 1) next = 2; if (cur.d == 2) next = 1; if (cur.d == 3) next = 4; if (cur.d == 4) next = 3;
                        map[ny][nx].d = next;
                    }
                }//if 양 끝
                else {// 양 끝이 아니라면
                    map[ny][nx].size += cur.s;
                    if (map[ny][nx].max_size < cur.s) {
                        map[ny][nx].max_size = cur.s;
                        map[ny][nx].d = cur.d;
                    }
                }//else 양 끝이 아님
            } //if 범위 안
        }//while
        for (int Y = 0; Y < N; Y++) {
            for (int X = 0; X < N; X++) {
                if (map[Y][X].size == 0) continue;
                q_info next;
                next.x = X; next.y = Y; next.s = map[Y][X].size; next.d = map[Y][X].d;
                q.push(next);
            }
        }
    }//for 시간만큼
    int q_end = q.size();
    for (int i = 0; i < q_end; i++) {
        ans += q.front().s;
        q.pop();
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        ans = 0;
        scanf("%d %d %d", &N, &M, &K);
        for (int i = 0; i < K; i++) {
            int x, y, size, dir;
            scanf("%d %d %d %d", &y, &x, &size, &dir);
            q_info qq;
            qq.x = x;
            qq.y = y;
            qq.d = dir;
            qq.s = size;
            q.push(qq);
            map[y][x].size = size;
        }
        bfs();
        printf("#%d %d\n", t, ans);
    }//for T
}