[C++] SWEA 5653 - 줄기세포배양

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo 

SW Expert Academy

<풀이>

1. 세포의 초기 상태와 배양 시간을 입력받고, 시뮬레이션을 돌린다.

2. 시간이 지난 후, 살아있는 줄기 세포의 갯수를 출력한다.

 

<해법>

단순한 시뮬레이션 처럼 보이지만, 문제를 풀 때 까다롭게하는 몇 가지 조건들이 있습니다. 이 조건들을 해결하는 저의 방법을 말씀드리겠습니다.

 

1. '배양 용기의 크기는 무한하다.'

=> 저는 이걸 읽고, '단순히 map[][], visited[][]와 같이 2차원 배열을 이용하는 것이 아니라, 다른 방식을 사용해서 정보를 저장해야 겠다.' 라는 생각을 하였습니다. 저는 set를 이용하여 visitied를 구현하였습니다.

2차원 배열을 이용하여 풀 수도 있습니다. 많은 분들이 2차원 배열을 이용하여 풀었습니다. 그렇지만, 저는 최대한 문제의 조건에 맞게 풀고 싶었습니다.(2차원 배열은 크기가 무한하지 않다고 생각해서...)

 

2. '여러개의 세포가 동시에 번식할 때, 생명력이 높은 세포가 셀을 차지한다.'

=> 저는 이걸 읽고, '단순히 큐에 넣고, 돌리는 방법만으로는 안된다.' 라는 생각을 하였습니다. 왜냐하면, 세포 간 우선순위가 존재하기 때문입니다. 저는 세포 생명력에 따라 큐 배열을 만들었고(생명력 최대치가 10이기 때문), 생명력이 높은 세포 큐부터 탐색을 진행해서 생명력이 높은 세포가 먼저 자리를 차지할 수 있도록 하였습니다.

 

#include <iostream>
#include <set>
#include <queue>
 
using namespace std;
 
//구조체 : 위치
struct pos { 
    int x, y;
};
 
//구조체 : 세포
struct cell {
    pos p;          //위치
    int timer;      //남은 생명
};
 
bool operator<(pos a, pos b) {
    if (a.x == b.x) {
        return a.y < b.y;
    }
    return a.x < b.x;
}
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int N, M, K;
int answer;
set<pos> visited;
queue<cell> q[11];
 
void simulation() {
    while (K--) {
 
        for (int i = 10; i > 0; i--) {
            int qSize = q[i].size();
 
            while (qSize--) {
 
                cell curCell = q[i].front();
                q[i].pop();
 
                //번식
                if (curCell.timer == 0) {
                    for (int j = 0; j < 4; j++) {
                        cell childCell = curCell;
                        childCell.p.x += dx[j];
                        childCell.p.y += dy[j];
                        childCell.timer = i;
 
                        //이미 세포가 차지하고 있는 경우
                        if (visited.find(childCell.p) != visited.end()) {
                            continue;
                        }
 
                        visited.insert(childCell.p);
                        q[i].push(childCell);
                    }
                }
 
                //세포 늙고, 아직 살아있는 경우만 다시 큐에 넣기
                cell nxtCell = curCell;
                nxtCell.timer--;
                if (nxtCell.timer != -i) {
                    q[i].push(nxtCell);
                }
            }
        }
    }
 
    //정답 갱신
    for (int i = 1; i < 11; i++) {
        answer += q[i].size();
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, M = 0, K = 0;
        answer = 0;
        visited.clear();
        for (int i = 1; i < 11; i++) {
            while (!q[i].empty()) {
                q[i].pop();
            }
        }
 
        //입력
        cin >> N >> M >> K;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int lifeTime = 0;
                cin >> lifeTime;
                if (lifeTime > 0) {
                    visited.insert({ i,j });
                    q[lifeTime].push({ {i,j}, lifeTime });
                }
            }
        }
 
        //해법
        simulation();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

구현과 BFS에 대해 알아볼 수 있는 문제였습니다.