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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl&categoryId=AV597vbqAH0DFAVl&categoryType=CODE&problemTitle=모의&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&& 

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA2382.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA2382
//
//  Created by Hwayeon on 2021/10/16.
//

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int N, M, K;
int area[100][100] = {0, };
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};

struct Community{
    int y;
    int x;
    int micro_num = 0;
    int dir;
};
struct cmp{
    bool operator()(Community c1, Community c2){
        if(c1.y == c2.y){
            if(c1.x == c2.x){
                return c1.micro_num < c2.micro_num;
            }
            return c1.x < c2.x;
        }
        return c1.y < c2.y;
    }
};
Community com;
priority_queue<Community, vector<Community>, cmp> communities;
int answer = 0;

int change_dir(int dir){
    int new_dir = -1;
    switch(dir){
        case 1:
            new_dir = 2;
            break;
        case 2:
            new_dir = 1;
            break;
        case 3:
            new_dir = 4;
            break;
        case 4:
            new_dir = 3;
            break;
    }
    return new_dir;
}

void move_community(){
    priority_queue<Community, vector<Community>, cmp> new_communities;
    while(!communities.empty()){
        com = communities.top();
        communities.pop();
        area[com.y][com.x]--;
        com.x += dx[com.dir];
        com.y += dy[com.dir];
        //빨간 셀에 도착한 경우,
        if(com.x == 0 || com.x == N-1 || com.y == 0 || com.y == N-1){
            com.dir = change_dir(com.dir);
            com.micro_num /= 2;
            if(com.micro_num == 0) continue;
        }
        new_communities.push(com);
        area[com.y][com.x]++;
    }
    while(!new_communities.empty()){
        com = new_communities.top();
        new_communities.pop();
        area[com.y][com.x]--;
        while(area[com.y][com.x] > 0){
            com.micro_num += new_communities.top().micro_num;
            new_communities.pop();
            area[com.y][com.x]--;
        }
        communities.push(com);
        area[com.y][com.x] = 1;
    }
}

void start_timer(){
    for(int m=0; m<M; m++){
        move_community();
    }
    while(!communities.empty()){
        com = communities.top();
        answer += com.micro_num;
        communities.pop();
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        memset(area, 0, sizeof(area));
        answer = 0;
        cin >> N >> M >> K;
        for(int i=0; i<K; i++){
            cin >> com.y >> com.x >> com.micro_num >> com.dir;
            communities.push(com);
            area[com.y][com.x]++;
        }
        start_timer();
        cout << "#" << test_case << " " << answer << endl;
    }

    return 0;
}

---

풀이 과정

풀이 시간 40분

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int N, M, K;
int area[100][100] = {0, };

//1-상, 2-하, 3-좌, 4-우
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};

struct Community{
    int y;
    int x;
    int micro_num = 0;
    int dir;
};
struct cmp{
    bool operator()(Community c1, Community c2){
    	//행 번호가 같은 경우,
        if(c1.y == c2.y){
        	//열 번호가 같은 경우,
            if(c1.x == c2.x){
            	//미생물 수가 많은 순서대로
                return c1.micro_num < c2.micro_num;
            }
            //열 번호가 큰 순서대로
            return c1.x < c2.x;
        }
        //행 번호가 큰 순서대로
        return c1.y < c2.y;
    }
};
Community com;
priority_queue<Community, vector<Community>, cmp> communities;
int answer = 0;

int change_dir(int dir){
    int new_dir = -1;
    switch(dir){
    	//상
        case 1:
            new_dir = 2;
            break;
        //하
        case 2:
            new_dir = 1;
            break;
        //좌
        case 3:
            new_dir = 4;
            break; 
        //우
        case 4:
            new_dir = 3;
            break;
    }
    return new_dir;
}

void move_community(){
	//이동 후의 군집들을 담는 우선순위 큐 
    priority_queue<Community, vector<Community>, cmp> new_communities;
    
    while(!communities.empty()){
        com = communities.top();
        communities.pop();
        //해당 위치의 군집 카운트 감소
        area[com.y][com.x]--;
        //군집 이동방향으로 한 칸 이동
        com.x += dx[com.dir];
        com.y += dy[com.dir];
        
        //빨간 셀에 도착한 경우,
        if(com.x == 0 || com.x == N-1 || com.y == 0 || com.y == N-1){
        	//이동방향을 반대로 바꾼다
            com.dir = change_dir(com.dir);
            //미생물 수가 절반 줄어든다
            com.micro_num /= 2;
            //미생물 수가 0이 되면 해당 군집이 사라진다
            if(com.micro_num == 0) continue;
        }
        //이동한 군집 new_communities에 추가
        new_communities.push(com);
        //area에 군집 카운팅
        area[com.y][com.x]++;
    }
    
    //2개 이상의 군집을 합친다
    while(!new_communities.empty()){
        com = new_communities.top();
        new_communities.pop();
        //해당 위치의 군집 카운트 감소
        area[com.y][com.x]--;
        
        //2개 이상의 군집이 있는 경우
        while(area[com.y][com.x] > 0){
        	//군집의 미생물 수를 합친다
            com.micro_num += new_communities.top().micro_num;
            new_communities.pop();
            //해당 위치의 군집 카운트 감소
            area[com.y][com.x]--;
        }
        //합쳐진 군집을 communities에 담는다
        communities.push(com);
        //area에 군집 카운팅
        area[com.y][com.x] = 1;
    }
}

void start_timer(){
	//M시간동안 군집 이동
    for(int m=0; m<M; m++){
        move_community();
    }
    //남은 군집의 미생물 수 카운팅
    while(!communities.empty()){
        com = communities.top();
        answer += com.micro_num;
        communities.pop();
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
    	//area와 answer 초기화
        memset(area, 0, sizeof(area));
        answer = 0;
        cin >> N >> M >> K;
        for(int i=0; i<K; i++){
            cin >> com.y >> com.x >> com.micro_num >> com.dir;
            //군집 추가 후, area에 군집 카운팅
            communities.push(com);
            area[com.y][com.x]++;
        }
        start_timer();
        cout << "#" << test_case << " " << answer << endl;
    }

    return 0;
}
//시간복잡도 = O(M*K) = O(M^2), 공간복잡도 = O(M*K)