https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl&
약친 곳이나 미생물의 이동은 코드를 참고하시면 되겠습니다.
미생물 격리에서 유의할 점은 서로 겹칠 때를 판단하는 것 입니다.
저는 두가지 방법으로 문제를 풀었습니다.
1.sort를 하여 우선순위를 정한 후 판단 배열을 미생물의 수를 기준으로 내림차순하면
따로 겹칠때 계산할 게 없습니다. 그냥 먼저 자리를 차지한 녀석에게 미생물의 수를 더하고
뒤에 온녀석은 없애면 그만입니다. 단점은 sort를 매 시간마다 해줘야하므로 시간이 좀 필요합니다 (565ms)
2.map배열을 3차원으로 하여 판단 map[x][y][0]은 미생물의 번호, map[x][y][1]은 미생물의 수로 한 후
겹칠때마다 서로 비교하여 넣어 줍니다. 이렇게 하면 시간은 좀 단축하여 풀 수 있습니다. (303ms)
단점은 머리를 좀 굴려야해서 실수가 발생할 수 있다는 점…ㅎㅎ;;
1.sort를 하여 우선순위를 정한 후 판단
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, k;
int map[101][101];//이동 후 자리
struct Info {
int x;
int y;
int num;
int dir;
}micro[1001];
bool comp(Info a, Info b) {//미생물의 수를 오름차순 정렬
return a.num > b.num;
}
int dx[] = { 0,-1,1,0,0 };
int dy[] = { 0,0,0,-1,1 };
queue <pair<int, int>> q;//map의 빠른 초기화를 위해 큐사용
void move() {
while (m--) {
for (int i = 0; i < k; i++) {
if (micro[i].num == 0) break;//0이면 뒤에도 다 0이므로 break
int x = micro[i].x;
int y = micro[i].y;
int num = micro[i].num;
int dir = micro[i].dir;
int nx = x + dx[dir];
int ny = y + dy[dir];
//약친곳
if (nx == 0 || ny == 0 || nx == n - 1 || ny == n - 1) {
num /= 2;
if (dir == 1 || dir == 3) dir += 1;
else dir -= 1;
micro[i].dir = dir;
micro[i].num = num;
}
//이동
if (map[nx][ny] == -1) {
map[nx][ny] = i;
q.push(make_pair(nx, ny));
}
else {//겹치는곳
micro[map[nx][ny]].num += num;
micro[i].num = 0;
continue;
}
micro[i].x = nx;
micro[i].y = ny;
}
sort(micro, micro + k, comp);//다시 정렬
while (!q.empty()) {//초기화
map[q.front().first][q.front().second] = -1;
q.pop();
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int test_case;
cin >> test_case;
for (int t = 1; t <= test_case; t++) {
//start
cin >> n >> m >> k;
for (int i = 0; i < 101; i++)
for (int j = 0; j < 101; j++)
map[i][j] = -1;//map -1로 초기화
for (int i = 0; i < k; i++)
cin >> micro[i].x >> micro[i].y >> micro[i].num >> micro[i].dir;
sort(micro, micro + k, comp);//정렬
move();
//end
int result = 0;
for (int i = 0; i < k; i++) {
if (micro[i].num > 0) result += micro[i].num;
else break;
}
cout << '#' << t << ' ' << result << '\n';
}
}
2.map배열을 3차원으로 하여 판단
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
//13:33
int n, m, k;
int map[101][101][2];//map[x][y][0]은 미생물의번호, [1]은 미생물 수
struct Info {
int x;
int y;
int num;
int dir;
}micro[1001];
int dx[] = { 0,-1,1,0,0 };
int dy[] = { 0,0,0,-1,1 };
queue <pair<int, int>> q;//map을 초기화시켜주기 위해
void move() {
while (m--) {
for (int i = 0; i < k; i++) {
if (micro[i].num == 0) continue;
int x = micro[i].x;
int y = micro[i].y;
int num = micro[i].num;
int dir = micro[i].dir;
int nx = x + dx[dir];
int ny = y + dy[dir];
//약친곳
if (nx == 0 || ny == 0 || nx == n - 1 || ny == n - 1) {
num /= 2;
if (dir == 1 || dir == 3) dir += 1;
else dir -= 1;
micro[i].dir = dir;
micro[i].num = num;
}
//이동
if (map[nx][ny][0] == -1) {
map[nx][ny][0] = i;
map[nx][ny][1] = num;
q.push(make_pair(nx, ny));
}
else {//겹치는곳
int tempi = map[nx][ny][0];
int tempNum = map[nx][ny][1];
if (tempNum > num) {//기존값이 더 크면
micro[tempi].num += num;
micro[i].num = 0;
continue;
}
else {//기존값이 더 작으면
map[nx][ny][0] = i;
map[nx][ny][1] = num;
micro[i].num += micro[tempi].num;
micro[tempi].num = 0;
}
}
micro[i].x = nx;
micro[i].y = ny;
}
while (!q.empty()) {//map초기화
map[q.front().first][q.front().second][0] = -1;
map[q.front().first][q.front().second][1] = 0;
q.pop();
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int test_case;
cin >> test_case;
for (int t = 1; t <= test_case; t++) {
//start
cin >> n >> m >> k;
for (int i = 0; i < 101; i++)
for (int j = 0; j < 101;j++)
map[i][j][0] = -1;
for (int i = 0; i < k; i++)
cin >> micro[i].x >> micro[i].y >> micro[i].num >> micro[i].dir;
move();
//end
int result = 0;
for (int i = 0; i < k; i++) {
if (micro[i].num > 0) result += micro[i].num;
else continue;
}
cout << '#' << t << ' ' << result << '\n';
}
}
- 나 혼자 말하고 나 혼자 듣는 말
….