[SWEA][모의 SW 역량테스트][C++] 2382 미생물 격리

문제

SWEA 모의 SW 역량테스트 - 2382 미생물 격리

SW Expert Academy

 

---

문제 풀이

접근 방식

매 시간마다 미생물 군집을 이동시켜야 하는 문제이므로, BFS 방식으로 문제를 해결하였다.

cluster 구조체를 만들어서 이동할 군집들의 위치(x, y)와 현재 시간(m)을 저장하여 큐에 넣어주었고,

map은 3차원 배열로 만들어서 map[x][y][0]에는 미생물의 수, map[x][y][1]에는 방향,

map[x][y][2]에는 겹치는 경우에 미생물 수가 가장 많은 군집의 미생물 수를 저장하였다.

 

미생물 군집의 정보를 입력 받을 때, 그 군집의 미생물 수와 방향은 map에 저장해주었고,

그 위치와 현재 시간인 0을 구조체에 저장하여 큐에 넣어주었다.

 

그 후, BFS 방식으로 매 시간마다 큐의 크기만큼 for문을 시행하며 copy_map에 군집들을 이동시켜주었다.

이동할 때는 3가지 조건을 고려하여야 한다.

 

1. 이동할 곳이 테두리 부분인 경우

   : 미생물 수를 반으로 줄이고, 방향을 반대로 바꿔주었다.

 

2. 군집이 겹치지 않는 경우

   : copy_map에 미생물 수와 방향을 저장하고, 큐에 이동한 위치에 있는 군집을 넣어주었다.

 

3. 군집이 겹치는 경우

   : map[x][y][0]에는 기존의 값에 현재 미생물의 수를 더해주었고,

     map[x][y][2]에 있는 값고 현재 값을 비교하여 현재 값이 더 크면 방향을 현재 방향으로 바꾸고,

     map[x][y][2]를 현재 미생물의 수로 바꿔주었다.

 

1시간의 이동을 완료한 후에는 map에 copy_map을 복사하여 map에 최종적인 이동 결과를 저장해주었고,

위의 과정을 현재 시간이 M이 될때까지 반복하였다. (매번 copy_map의 값을 모두 0으로 초기화한 후 수행)

현재 시간이 M이 되면 이동을 완료한 것이므로, 그 때의 미생물 수를 모두 더해주어 답을 구하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
struct cluster {
    int x, y, m;
};
 
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
 
int main(int argc, char** argv) {
    int test_case;
    int T, N, M, K, x, y, k, d, total, nx, ny;
    cin >> T;
    int map[100][100][3];
    int copy_map[100][100][3];
    queue<cluster> q;
 
    for (test_case = 1; test_case <= T; ++test_case) {
        memset(map, 0, sizeof(map));
        cin >> N >> M >> K;
        for (int i = 0; i < K; i++) {
            cin >> x >> y >> k >> d;
            map[x][y][0] = k;
            map[x][y][1] = d;
            q.push({ x,y,0 });
        }
 
        total = 0;
        while (!q.empty()) {
            int len = q.size();
            memset(copy_map, 0, sizeof(copy_map));
            for (int i = 0; i < len; i++) {
                cluster now = { q.front().x, q.front().y, q.front().m };
                k = map[now.x][now.y][0];
                d = map[now.x][now.y][1];
                q.pop();
 
                if (now.m == M) {
                    total += map[now.x][now.y][0];
                    continue;
                }
 
                nx = now.x + dir[d - 1][0];
                ny = now.y + dir[d - 1][1];
 
                if (nx == 0 || nx == N - 1 || ny == 0 || ny == N - 1) { // 테두리 부분인 경우
                    k /= 2;
                    if (k == 0) continue;
                    if (d == 1 || d == 3)
                        d++;
                    else
                        d--;
                }
 
                if (copy_map[nx][ny][0] == 0) { // 겹치지 않는 경우
                    copy_map[nx][ny][0] = k;
                    copy_map[nx][ny][1] = d;
                    q.push({ nx, ny, now.m + 1 });
                }
                else {  // 겹치는 경우
                    if (copy_map[nx][ny][2] == 0)
                        copy_map[nx][ny][2] = copy_map[nx][ny][0];
                    if (copy_map[nx][ny][2] < k) {
                        copy_map[nx][ny][2] = k;
                        copy_map[nx][ny][1] = d;
                    }
                    copy_map[nx][ny][0] += k;
                }
            }
            memcpy(map, copy_map, sizeof(map));
        }
        cout << "#" << test_case << " " << total << endl;
    }
    return 0;
}

실행 결과