ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] #2382 _ 미생물 격리
    Problem Solving/SWEA 2019. 10. 29. 18:05

    [미생물 격리] https://swexpertacademy.com/main/code/problem/problemDetail.do

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

    시뮬레이션 문제이다.

     

    k_info라는 구조체를 선언하여 미생물의 군집의 정보를 저장하였다.

    map은 군집의 위치에 미생물의 수를 나타내고 있다.

     

    군집이 이동하기 전 해당 위치의 map 값을 0으로 만들어 주고

    모든 군집의 이동이 끝난 후 map에 각 군집의 미생물 수를 해당 좌표에 뿌려주었다.

    이를 구현하기 위해 tmp 벡터를 사용하였다.

     

    예를 들어,

    A군집이 이동하고자하는 자리에 이동하지 않은 B군집이 있는 경우에는 합쳐지면 안된다.

    따라서, tmp 벡터에 임시로 저장해두고, 모든 이동이 끝난 후 좌표에 뿌려주었고

    군집이 합쳐지면 v_k 벡터에서 삭제하여 하나의 군집으로 만들어 주었다.

     

    [ 소스 코드 ]

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    #define MAX 100
    
    using namespace std;
    
    typedef struct k_info {
    	int y, x, count, d;
    }K_info;
    
    int dx[] = { 0,0,0,-1,1 }, dy[] = { 0,-1,1,0,0 };
    int N, M, K;
    int map[MAX][MAX];
    vector<K_info> v_k;
    
    int solve();
    int getTotalK();
    int main() {
    	int T, y, x, cnt, d;
    
    	scanf("%d", &T);
    	for (int i = 1; i <= T; i++) {
    		scanf("%d %d %d", &N, &M, &K);
    		for (int j = 0; j < K; j++) {
    			scanf("%d %d %d %d", &y, &x, &cnt, &d);
    			map[y][x] = cnt;
    			v_k.push_back({ y,x,cnt,d });
    		}
    
    		printf("#%d %d\n", i, solve());
    	}
    
    	return 0;
    }
    
    int solve() {
    	vector<K_info> tmp;
    
    	for (int i = 0; i < M; i++) {
    		for (int j = 0; j < v_k.size(); j++) {
    			map[v_k[j].y][v_k[j].x] = 0;
    			v_k[j].x += dx[v_k[j].d];
    			v_k[j].y += dy[v_k[j].d];
    			
    			if (v_k[j].x <= 0 || v_k[j].y <= 0 || v_k[j].x >= N - 1 || v_k[j].y >= N - 1) {
    				v_k[j].count /= 2;
    				map[v_k[j].y][v_k[j].x] = v_k[j].count;
    				if (v_k[j].d == 1) v_k[j].d = 2;
    				else if (v_k[j].d == 2) v_k[j].d = 1;
    				else if (v_k[j].d == 3) v_k[j].d = 4;
    				else v_k[j].d = 3;
    				continue;
    			}
    			if (map[v_k[j].y][v_k[j].x] > 0) tmp.push_back(v_k[j]);
    			else map[v_k[j].y][v_k[j].x] = v_k[j].count;
    		}
    
    		for (int j = 0; j < tmp.size(); j++) {
    			if (map[tmp[j].y][tmp[j].x] == 0) {
    				map[tmp[j].y][tmp[j].x] = tmp[j].count;
    				tmp.erase(tmp.begin() + j);
    				j--;
    			}
    			else {
    				map[tmp[j].y][tmp[j].x] += tmp[j].count;
    			}
    		}
    
    		for (int j = 0; j < tmp.size(); j++) {
    			int tmp_d, tmp_count = -1;
    
    			for (int k = 0; k < v_k.size(); k++) {
    				if (tmp[j].x == v_k[k].x && tmp[j].y == v_k[k].y) {
    					if (v_k[k].count > tmp_count) {
    						tmp_count = v_k[k].count;
    						tmp_d = v_k[k].d;
    					}
    					v_k.erase(v_k.begin() + k);
    					k--;
    				}
    			}
    			v_k.push_back({ tmp[j].y, tmp[j].x, map[tmp[j].y][tmp[j].x], tmp_d });
    		}
    		tmp.clear();
    	}
    	return getTotalK();
    }
    
    int getTotalK() {
    	int val = 0;
    
    	for (int i = 0; i < v_k.size(); i++) {
    		val += v_k[i].count;
    		map[v_k[i].y][v_k[i].x] = 0;
    	}
    	v_k.clear();
    
    	return val;
    }

    'Problem Solving > SWEA' 카테고리의 다른 글

    [SWEA] #2477 _ 차량 정비소  (0) 2019.10.29
    [SWEA] #2383 _ 점심 식사시간  (0) 2019.10.29
    [SWEA] #2382 _ 미생물 격리  (0) 2019.10.29
    [SWEA] #2117 _ 홈 방범 서비스  (0) 2019.10.29
    [SWEA] #2115 _ 벌꿀채취  (0) 2019.10.29
    [SWEA] #2105 _ 디저트 카페  (0) 2019.10.29

    댓글 0

@Jo Grini's Blog :)