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

[모의 SW 역량테스트] 미생물 격리

---

1. 이해하기

• 미생물들이 구역을 벗어나는걸 방지하기 위해, 가장 바깥쪽 가장자리 부분에는 특수한 약품이 칠해져 있다.
• 미생물의 움직임은 상, 하, 좌, 우 중 하나이다.
• 처음에 미생물은 약품이 칠해진 부분에 위치하지 않는다.
• 미생물 군집은 1시간마다 이동방향에 있는 다음 셀로 이동한다.
• 미생물 군집이 이동 후 약품이 칠해진 곳에 도착하면 군집 내 미생물의 절반이 죽고, 이동방향이 반대로 바뀐다.
• 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다. 합쳐 진 미생물의 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다.
• M시간 후 남아 있는 미생물 수의 총합을 구하는 문제.
• 시뮬레이션 문제.

---

2. 구현하기

• 미생물의 움직임을 구현한다.

  • 미생물 군집이 약품이 칠해진 곳에 도달하면 미생물 수를 반감하고 이동 방향을 반대로 바꾼다.
  • 맵에 최대 수의 미생물 군집의 인덱스와 수를 저장한다.
  • 같은 위치에 도달하면 군집을 합치고 최대 수의 미생물 군집의 이동 방향으로 설정한다.

  int change_dir(int dir) {
      if(dir == 1) return 2;
      if(dir == 2) return 1;
      if(dir == 3) return 4;
      if(dir == 4) return 3;
  }
  
  void move() {
      memset(map,0,sizeof(map));
      for(int i = 1; i <= K; i++) {
          Cell& now = cell[i];
          if(now.cnt == 0) continue;
          now.x+=dx[now.dir]; now.y+=dy[now.dir];
          if(now.x == 0 or now.y == 0 or now.x == N-1 or now.y == N-1) {
              now.cnt/=2; now.dir = change_dir(now.dir);
          } else {
              if(map[now.x][now.y][0] == 0) {
                  map[now.x][now.y][0] = i;
                  map[now.x][now.y][1] = now.cnt;
              } else {
                  int index = map[now.x][now.y][0], cnt = map[now.x][now.y][1];
                  if(cnt > now.cnt) {
                      cell[index].cnt += now.cnt; now.cnt = 0;
                  } else if(cnt < now.cnt){
                      map[now.x][now.y][0] = i;
                      map[now.x][now.y][1] = now.cnt;
                      now.cnt+=cell[index].cnt;
                      cell[index].cnt = 0;
                  }
              }
          }
      }
  }

• M시간을 보낸 후 미생물 수의 합을 계산한다.

  int calc_cell_cnt() {
      int ret = 0;
      for(int i = 1; i <= K; i++) {
          ret += cell[i].cnt;
      }
      return ret;
  }
  
  int simulate() {
      for(int i = 0; i < M; i++) {
          move();
      }
      return calc_cell_cnt();
  }

---

3. 전체 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct Cell{
    int x,y,cnt,dir;
};
int map[100][100][2];
Cell cell[1001];
int dx[] = {0,-1,1,0,0};
int dy[] = {0,0,0,-1,1};
int N,M,K;

int change_dir(int dir) {
    if(dir == 1) return 2;
    if(dir == 2) return 1;
    if(dir == 3) return 4;
    if(dir == 4) return 3;
}

void move() {
    memset(map,0,sizeof(map));
    for(int i = 1; i <= K; i++) {
        Cell& now = cell[i];
        if(now.cnt == 0) continue;
        now.x+=dx[now.dir]; now.y+=dy[now.dir];
        if(now.x == 0 or now.y == 0 or now.x == N-1 or now.y == N-1) {
            now.cnt/=2; now.dir = change_dir(now.dir);
        } else {
            if(map[now.x][now.y][0] == 0) {
                map[now.x][now.y][0] = i;
                map[now.x][now.y][1] = now.cnt;
            } else {
                int index = map[now.x][now.y][0], cnt = map[now.x][now.y][1];
                if(cnt > now.cnt) {
                    cell[index].cnt += now.cnt; now.cnt = 0;
                } else if(cnt < now.cnt){
                    map[now.x][now.y][0] = i;
                    map[now.x][now.y][1] = now.cnt;
                    now.cnt+=cell[index].cnt;
                    cell[index].cnt = 0;
                }
            }
        }
    }
}

int calc_cell_cnt() {
    int ret = 0;
    for(int i = 1; i <= K; i++) {
        ret += cell[i].cnt;
    }
    return ret;
}

int simulate() {
    for(int i = 0; i < M; i++) {
        move();
    }
    return calc_cell_cnt();
}

void input() {
    cin >> N >> M >> K;
    for(int i = 1; i <= K; i++) {
        cin >> cell[i].x >> cell[i].y >> cell[i].cnt >> cell[i].dir;
    }
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        cout << '#' << t << ' ' << simulate() << '\n';
    }
    return 0;
}