SWEA 2382번 [모의 SW 역량테스트] 미생물 격리 C++ 구현, 시뮬레이션

리뷰

자꾸 50개의 테스트 케이스에서 43개만 맞아서 고민을 했었는데, 합쳐지는 경우가 2개의 미생물 뿐만 아닌, 3개의 미생물인 케이스가 있었다.

SW Expert Academy

 

문제 풀이

각 테스트 케이스에 대해서 init, input, solution 함수로 나누어 풀이를 하고 테스트 케이스에 대한 답을 도출하였다.

1. init()

1. 정답을 도출할 ans 변수를 0으로 초기화 해준다, 맵을 나타낼 2차 배열 lst를 모두 0으로 초기화 해준다.

 

2. input()

1. n, m, k 값을 입력 받고, 미생물에 대한 정보를 1번 인덱스 부터 k번 인덱스로 받아와 bugs 배열에 저장해 준다.
2. 또한 맵의 받아온 미생물의 좌표에 해당 미생물의 인덱스를 기재해 준다.

 

3. solution()

1. m번의 while 루프를 실행해 주고, 맵 전체를 탐색하여 미생물이 위치할 경우 해당 미생물 인덱스를 큐에 추가해준다.
2. 이후 해당 미생물이 있던 좌표를 모두 0으로 만들어 주고, 탐색이 종료되면 bfs 함수를 실행해 준다.
3. while 루프가 종료된 후 맵에 남아있는 미생물의 군집 수를 ans에 모두 더해준다.

 

4. bfs()

1. 큐에 미생물이 존재하지 않을 때 까지 while 루프를 돌려준다.
2. bugs 배열에서 index를 통해 구조체 bug를 참조해 오고 해당 미생물이 가진 방향으로 한칸 이동 시킨다.
3. 만약 이동한 좌표가 가장자리 일 경우 군집 수를 절반으로 줄인 후 반대 방향으로 바꾸어 준다.
4. 이동 좌표를 Union 배열의 인덱스에 알맞게 배치하여 미생물의 인덱스를 push 해준다.
5. 미생물의 위치와 군집 수, 방향을 업데이트 해준다.
6. while이 종료될 경우 doUnion 함수를 실행해 준다.

5. doUnion()

1. Union 배열을 탐색해 준다. 만약 특정 좌표에 미생물이 존재할 경우 해당 배열에서 가장 큰 미생물을 찾아준다.
2. 만약 미생물이 한개일 경우 해당 미생물이 가장 크므로 맵의 좌표에 해당 미생물을 배치해 준다.
3. 만약 미생물이 여러개일 경우 가장 큰 미생물에 다른 미생물의 군집수를 추가하고 가장 큰 미생물을 배치해 준다.
4. 미생물 배치가 끝난 경우 가장 큰 미생물의 군집 수를 업데이트 해준 후 벡터를 초기화 해준다.

 

solution 함수가 종료되면 각 테스트 케이스에 맞는 ans값을 출력해 주면 된다.

 

참고 사항

같은 좌표로 이동하는 미생물이 2개인 경우에는 상관이 없지만 3개인 경우는 케이스를 잘 고려해야 한다.

만약 군집 수가 50, 100, 120인 미생물 a, b, c가 있을 때 순차적으로 계산을 하게 되면 a와 b를 먼저 비교하여 150이 될 경우 c보다 크므로 b 미생물이 가장 크다는 판단을 내리게 된다.

하지만 해당 좌표로 모인 미생물을 비교하는 작업은 한번에 이루어 져야 한다.

 

정답 코드

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>

using namespace std;

int lst[100][100];
int t, n, m, k, ans;

int dx[] = { 0, -1, 1, 0, 0 };
int dy[] = { 0, 0, 0, -1, 1 };

struct BUG {
	int x, y, c, d, idx;
};

BUG bugs[1001];
vector<int> Union[100][100];
queue<int> q;

void init() {
	ans = 0;
	memset(lst, 0, sizeof(lst));
}

void input() {
	cin >> n >> m >> k;
	for (int i = 1; i <= k; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		bugs[i] = { a, b, c, d, i }; // 미생물 정보 받아오고 배열에 저장
		lst[a][b] = i; // 맵에는 해당 미생물의 인덱스 배치
	}
}

void doUnion() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!Union[i][j].empty()) { // 해당 좌표에 이동할 미생물이 1개 이상 존재할 경우
				int max_cc = 0, sum_cc = 0, max_idx = 0;
				for (k = 0; k < Union[i][j].size(); k++) { // 군집이 가장 큰 미생물 찾기
					BUG& bug = bugs[Union[i][j][k]];
					if (max_cc < bug.c) {
						max_cc = bug.c;
						max_idx = bug.idx;
					}
					sum_cc += bug.c;
				}
				BUG& bug = bugs[max_idx]; // 대빵 미생물에 모든걸 합쳐준다
				lst[i][j] = bug.idx; 
				bug.x = i, bug.y = j, bug.c = sum_cc;
				Union[i][j].clear(); // 다음 탐색을 위한 벡터 청소
			}
		}
	}
	
}

void bfs() {
	while (!q.empty()) { // 미생물이 큐에 남아있지 않을 때 까지 이동 시작
		int index = q.front(); q.pop();
		BUG& bug = bugs[index]; // 미생물의 주소 참조
		int cd = bug.d, cc = bug.c, ci = bug.idx;
		int nx = bug.x + dx[cd], ny = bug.y + dy[cd]; // 현재 미생물의 방향으로 한칸 이동
		if (nx == 0 || ny == 0 || nx == n - 1 || ny == n - 1) { // 벽에 닿은 경우
			cc /= 2; // 군집 수 절반으로 줄임
			if (cd % 2) cd += 1; // 반대 방향으로 변환
			else cd -= 1;
		}
		Union[nx][ny].push_back(ci); // 미생물 합치기 위한 벡터로 push
		bug.x = nx, bug.y = ny, bug.c = cc, bug.d = cd; // 현재 미생물 주소값 업데이트
	}
	doUnion(); // 저장된 미생물 정보 합치기
}

void solution() {
	while (m--) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (lst[i][j]) { // 미생물 싹다 긁어다가 큐에 해당 미생물의 인덱스 추가
					q.push({ lst[i][j] });
					lst[i][j] = 0; // 맵 다시 싹 0으로 만들기
				}
			}
		}
		bfs(); // 미생물 이동 시작
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (lst[i][j]) ans += bugs[lst[i][j]].c; // 현재 맵에 남아있는 미생물의 개수 카운트
		}
	}
}

int main() {
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		init(); // 초기화
		input(); // 입력
		solution(); // 시뮬레이션
		cout << "#" << tc << " " << ans << "\n";
	}
}