[SWEA] 5653. 줄기세포 배양

문제 접근

평소에 푸는 스타일대로 문제를 풀었더니 49개 테케까지만 통과되고, 시간 초과 오류가 발생했다.
배열 순회 대신 큐를 써서 BFS로 구현해야 겠다는 생각이 들었지만
아래 쟁점을 고려하기 힘들어서 참고를 많이 했다. 시간도 많이 썼다.

쟁점

1. 활성화 세포가 번식할 때, 한 곳에 동시에 번식할 수가 있는데 그때는 생명력 수치가 높은 줄기세포만 해당 그리드 셀을 차지해야 한다.
2. 큐는 인덱스를 통한 참조가 안 되는데, 원하는 세포를 어떻게 traverse 할 것인가?

< priority_queue >와 < vector >를 사용하여 푼 풀이를 참고했다.
우선순위 큐를 사용한다면 위 쟁점을 다음과 같이 해결할 수 있다.

1. 활성화 세포를 생명력 수치가 높은 순으로 정렬한 다음, 빈 공간에만 번식하도록 한다.
2. 전체 세포를 관리하는 자료구조는 벡터로 구성하여 traverse가 가능하도록 하고, 각 iteration마다 활성화 세포를 priority_queue를 사용하여 관리하였다.

또 이 문제는 특이하게 격자의 범위가 주어지지 않았는데, 처음에 주어지는 범위의 최대값이 50이고, 배양 시간 K의 최대값이 300이기 때문에 격자의 크기를 충분히 주고 중앙에서 시작하도록 하였다.

뱀 문제처럼 'X시간' 에 대한 타이밍을 맞추는 게 중요하다.
나는 처음에 inactive, active, state변수를 두어 문제를 풀었는데, 이렇게 하지 않아도 된다.

우선순위 큐의 STL을 알고 사용할 수 있으면 코드의 단순화가 가능해 보인다.

그리고 vector를 비울 때는 vector.clear()를 사용하면 된다.
전역변수로 vector를 사용할 땐 vector.clear()를 통해 초기화 해주는 걸 잊지 말자.

풀이

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define MAX 400
#define SCALE MAX/2
using namespace std;

typedef struct cell {
	int x;
	int y;
	int X;
	int t;
} cell;

struct cmp {
	bool operator()(cell a, cell b) {
		return a.X < b.X;
	}
};

int N, M, K, T, rst, dead;
int map[MAX][MAX];
vector<cell> Cell;
priority_queue<cell, vector<cell>, cmp> activation;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

void input() {
	memset(map, 0, sizeof(map));
	Cell.clear();
	
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int X;
			cin >> X;
			if (X == 0) continue;
			Cell.push_back({ i + SCALE, j + SCALE, X, X });
			map[i + SCALE][j + SCALE] = X;
		}
	}
	dead = 0;
}

void solve() {
	while(K-- > 0) {
		for (int i = 0; i < Cell.size(); i++) {
			Cell[i].t--;
			if (Cell[i].t == -1) {
				activation.push(Cell[i]);
			}
			if (Cell[i].t == -Cell[i].X) {
				dead++;
			}
		}

		while (!activation.empty()) {
			int x = activation.top().x;
			int y = activation.top().y;
			int X = activation.top().X;
			activation.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (map[nx][ny] == 0) {
					map[nx][ny] = X;
					Cell.push_back({ nx, ny, X, X });
				}
			}
		}
	}
	rst = Cell.size() - dead;
}

int main() {
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		input();
		solve();
		cout << "#" << tc << " " << rst << endl;
	}
}

최초 풀이

#include <iostream>
#include <cstring>
#include <vector>
#define MAX 400
#define SCALE MAX/2
using namespace std;

typedef struct cell {
    int x;
    int y;
    int inactive;
    int active;
    int life;
    int state;
    int num;
}cell;

vector<cell> Cell; 
vector<cell> nCell;
int N, M, K, T, rst;
int map[MAX][MAX];
int nmap[MAX][MAX];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

void input() {
    cin >> N >> M >> K;
    int num = 0;
    memset(map, -1, sizeof(map));
    while (!Cell.empty()) {
        Cell.pop_back();
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int life;
            cin >> life;
            if (life == 0) continue;
            int num = Cell.size();
            cell tmp = { i + SCALE, j + SCALE, life, life, life, 0, num };
            Cell.push_back(tmp);
            map[i + SCALE][j + SCALE] = num;
        }
    }

}

void move() {
    memset(nmap, -1, sizeof(nmap));
    while (!nCell.empty()) {
        nCell.pop_back();
    }

    for (int idx = 0; idx < Cell.size(); idx++) {
        if (Cell[idx].state != 1) continue; // active cell
        int x = Cell[idx].x;
        int y = Cell[idx].y;
        int life = Cell[idx].life; // 겹치는 경우

        for (int i = 0; i < 4; i++) { // 상하좌우로 확인
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (map[nx][ny] != -1) continue; // 이미 다른 줄기세포가 있는 경우
            if (nmap[nx][ny] != -1) { // 동시에 번식하는 경우
                
                if (nCell[nmap[nx][ny]].life > life) continue; // 기존 세포의 생명력 수치가 더 클 경우
                
                cell tmp = { nx, ny, life, life, life, 0, nCell.size() };
                nCell.push_back(tmp);
                nmap[nx][ny] = tmp.num;

            }
            else { // 내가 번식하려고 하는 경우
                cell tmp = { nx, ny, life, life, life, 0, nCell.size() };
                nCell.push_back(tmp);
                nmap[nx][ny] = tmp.num; // 내 정보 저장
            }
        }
    }

}

void adjust() {
    for (int idx = 0; idx < Cell.size(); idx++) {
        if (Cell[idx].state == 0) {
            if (--Cell[idx].inactive == 0) Cell[idx].state = 1;
        }
        else if (Cell[idx].state == 1) {
            Cell[idx].active--;
        }
    }
}

void cal_rst() {
    rst = 0;
    for (int idx = 0; idx < Cell.size(); idx++) {
        if (Cell[idx].state == 2) continue;
        rst++;
    }
}


void solve() {
    while (K-- > 0) {
        move();
        adjust();
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++) {
                if (nmap[i][j] == -1) continue;
                int num = Cell.size();
                Cell.push_back(nCell[nmap[i][j]]);
                map[i][j] = num;
            }
        }

        for (int idx = 0; idx < Cell.size(); idx++)
            if (Cell[idx].active == 0) Cell[idx].state = 2;

     }
    cal_rst();
}

int main() {
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        input();
        solve();
        cout << "#" << tc << " " << rst << endl;
    }
}