문제 출처
- https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl
난이도
- 하 – (중) – 상 – 최상 – 풀지 못함
문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)
- N x N Matrix에 미생물 집단이 있다. 각 미생물 집단은 상, 하, 좌, 우로만 움직일 수 있고, Matrix 끝에 도달하게 되면 절반의 미생물이 죽고 이동 방향을 반대로 바꾸게 된다. 그리고 여러 집단의 미생물이 한 위치에서 만나게 되면 큰 집단에 흡수되어 버린다. 특정 시간이 흐른 후 남아 있는 미생물의 수를 계산하는 문제이다. SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 더 상세히 문제를 작성하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.
후기
- 미생물 문제는 아주 어렵다고 판단되지는 않는다. 대학원을 다니면서 Computer Architecture Simulator를 사용해 보았는데, 본 문제는 같은 방법을 사용하여 해결 가능한 문제이다. 하지만, 코딩을 하면서 한 가지 정도의 실수가 있었다.
- 미생물 집단이 한 곳에서 만나는 부분을 계산하기 위해서 History 정보를 저장하는 부분을 만들어서 문제를 해결하였다. 매시간 연산이 끝난 후 History 정보를 초기화해야 하는데 중간에 초기화를 하도록 만들어서 다른 미생물 집단의 수를 계산하는데 연산 에러가 발생하였다. 항상 History 정보를 초기화하는 시점을 명확하게 정하고 코딩을 시작할 필요가 있다.
코드
- 매시간 미생물 이동 방향을 계산하여 총 미생물 수 계산하는 부분
- 실행 시간: 90ms (제일 빠른 코드 대비 30배(3ms) 느림)
#include <stdio.h>
//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable: 4996)
#define MAXSIZE 100
#define MAXCELL 1000
//MK: 미생물 이동 방향을 계산하기 위해서 사용
int dir[5][2] = { {0,0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
//MK: 여러개의 집단이 한 곳에서 만나는 위치를 확인하기 위해 사용
int maxHistoryId[MAXSIZE][MAXSIZE];
int maxHistorySize[MAXSIZE][MAXSIZE];
int inputSize;
int cPtr[MAXCELL][4];
int numCell;
int clock;
void init() {
for (int i = 0; i < inputSize; i++) {
for (int j = 0; j < inputSize; j++) {
maxHistoryId[i][j] = -1;
maxHistorySize[i][j] = 0;
}
}
}
//MK: 매 시간 미생물 집단의 이동을 계산하는 부분
int simulate() {
while (clock > 0) {
clock--;
for(int i = 0; i < numCell; i++){
if (cPtr[i][2] != 0) {
int y = cPtr[i][0];
int x = cPtr[i][1];
int nextY = y + dir[cPtr[i][3]][0];
int nextX = x + dir[cPtr[i][3]][1];
if (nextY < 0) {
nextY = 1;
cPtr[i][3] = 2;
}
else if (nextX < 0) {
nextX = 1;
cPtr[i][3] = 4;
}
else if (nextY >= inputSize) {
nextY = inputSize - 2;
cPtr[i][3] = 1;
}
else if (nextX >= inputSize) {
nextX = inputSize - 2;
cPtr[i][3] = 3;
}
//maxHistoryId[y][x] = -1; //MK: History 중간에 업데이트 하는 경우 미생물의 수를 잘못 계산함.
//maxHistorySize[y][x] = 0;
if (maxHistoryId[nextY][nextX] == -1) {
maxHistoryId[nextY][nextX] = i;
maxHistorySize[nextY][nextX] = cPtr[i][2];
}
else {
int ptr = maxHistoryId[nextY][nextX];
if (maxHistorySize[nextY][nextX] > cPtr[i][2]) {
cPtr[ptr][2] += cPtr[i][2];
cPtr[i][2] = 0;
}
else {
maxHistoryId[nextY][nextX] = i;
maxHistorySize[nextY][nextX] = cPtr[i][2];
cPtr[i][2] += cPtr[ptr][2];
cPtr[ptr][2] = 0;
}
}
cPtr[i][0] = nextY;
cPtr[i][1] = nextX;
}
}
int tmp = 0;
for (int i = 0; i < numCell; i++) {
if (cPtr[i][2] != 0) {
maxHistoryId[cPtr[i][0]][cPtr[i][1]] = -1;
int y = cPtr[i][0];
int x = cPtr[i][1];
if (x == 0 || y == 0 || x == inputSize-1 || y == inputSize-1) {
//printf("(B) %d %d\n", i, cPtr[i][2]);
cPtr[i][2] /= 2;
//printf("(A) %d %d\n", i, cPtr[i][2]);
}
tmp += cPtr[i][2];
}
}
//printf("%d %d\n", clock, tmp);
}
int ret = 0;
for (int i = 0; i < numCell; i++) {
ret += cPtr[i][2];
}
return ret;
}
int main() {
freopen("input.txt", "r", stdin);
int testCase = 0;
scanf("%d", &testCase);
for (int m = 1; m <= testCase; m++) {
scanf("%d %d %d", &inputSize, &clock, &numCell);
init();
for (int i = 0; i < numCell; i++) {
scanf("%d %d %d %d", &cPtr[i][0], &cPtr[i][1], &cPtr[i][2], &cPtr[i][3]);
maxHistorySize[cPtr[i][0]][cPtr[i][1]] = cPtr[i][2];
}
printf("#%d %d\n", m, simulate());
}
return 0;
}