-
[SWEA] 2382 미생물 격리문제 풀이 2020. 5. 7. 20:50
2382 미생물 격리
풀이)
백준 17143 낚시왕 문제랑 똑같이 풀었다.
이차원 vector을 사용해서 중복된 위치의 군집을 해결해준다는 것이 핵심이다.
코드)
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include<stdio.h>#include <vector>#include <algorithm>using namespace std;struct virus {//세로위치, 가로위치, 미생물 수, 이동방향, 바이러스 구별 인덱스int y, x, num, dir, idx;virus(int y, int x, int num, int dir,int idx) {this->y = y;this->x = x;this->num = num;this->dir = dir;this->idx = idx;}};vector <virus> map[100][100];int dy[5] = { 0,-1,1,0,0 };int dx[5] = { 0,0,0,-1,1 };bool cmp(const virus &a, const virus &b) {return a.num > b.num;}int main() {//freopen("sample_input.txt", "r", stdin);int T = 0;scanf("%d", &T);for (int test_case = 1; test_case <= T; test_case++) {int n, m, k;scanf("%d %d %d", &n, &m, &k);vector<virus> vi;for (int i = 0; i < k; i++) {int y, x, n, d;scanf("%d %d %d %d", &y, &x, &n, &d);vi.push_back({ y,x,n,d,i });}while (m--){//1.미생물이동for (int i = 0; i < k; i++) {if (vi[i].num == 0) continue;//이미 죽은 군집이면 passvi[i].y += dy[vi[i].dir];vi[i].x += dx[vi[i].dir];if (vi[i].y < 1 || vi[i].y >= n - 1 || vi[i].x < 1 || vi[i].x >= n - 1) {//약품이 칠해진 셀vi[i].num /= 2;//절반이 죽고//방향을 반대로 바꿈if (vi[i].dir == 1 || vi[i].dir == 3) {vi[i].dir += 1;}else {vi[i].dir -= 1;}}if (vi[i].num > 0) {//미생물의 수가 0보다 많다면map[vi[i].y][vi[i].x].push_back(vi[i]);//지도에 미생물 삽입}}//2.미생물의 군집이 2개 이상 모여있을 경우for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (map[i][j].size() > 1) {sort(map[i][j].begin(), map[i][j].end(), cmp);//미생물의 수들로 내림차순virus winner = map[i][j][0];//군집중 가장 미생물 수가 많은 군집for (int t = 1; t < map[i][j].size(); t++) {vi[winner.idx].num += map[i][j][t].num;//미생물수가 가장많은 군집에 합쳐짐vi[map[i][j][t].idx].num = 0;}}}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {map[i][j].clear();}}}//살아남은 군집의 미생물 수 더하기int result = 0;for (int i = 0; i < k; i++) {if (vi[i].num == 0) continue;result += vi[i].num;}printf("#%d %d\n", test_case, result);}return 0;}cs '문제 풀이' 카테고리의 다른 글
[SWEA] 1952. 수영장 (0) 2020.05.08 [SWEA] 1953 탈주범 검거 (0) 2020.05.08 [SWEA] 2477 차량 정비소 (0) 2020.05.06 [SWEA] 2112. 보호필름 (0) 2020.05.04 [SWEA]2105 디저트 까페 (0) 2020.05.01