SWEA 5648번 [모의 SW 역량테스트] 원자 소멸 시뮬레이션 C++ 구현, 시뮬레이션

리뷰

 

방향 배열을 사용한 전형적인 시뮬레이션 문제

 

문제 풀이

1. 전역변수로 원자의 개수 n, 남은 원자의 개수 cnt, 정답을 출력할 ans, 맵 배열 lst, 방향 배열을 설정해 주었다.
2. 좌표의 범위는 -1000 ~ 1000이지만 -인덱싱을 방지하기 위해 +1000을 해준다.
3. 추가로 원자가 만나지 않고 지나치는 경우를 방지하기 위해 *2를 해준다. 즉, 좌표의 범위는 4000 * 4000이다.
4. 원자의 정보를 담을 구조체 Atom과 위치를 나타낼 구조체 Pos를 만들고 원자 벡터 atoms를 초기화해 주었다.
5. init 함수를 통해 cnt, ans를 0으로 초기화 하고 atoms배열 및 맵 정보를 테케마다 초기화 해준다.
6. input 함수를 통해 n값을 입력 받고 n개의 원자 정보를 atoms 벡터에 추가해 준 뒤 맵에 존재를 표시해 준다.
7. Atom구조체는 좌표 x, y 원자의 방향 dir 원자의 에너지 e 원자의 생존여부 life로 이루어져 있다.
8. simulation 함수를 통해 각 원자를 이동시켜 준다. 원자가 존재한다면 while루프를 계속 돌려준다.
9. 모든 원자를 순회한다. 이때 원자의 life가 0이라면 이미 소멸된 상태이므로 continue 처리해 주면 된다.
10. 각 원자가 맵 범위에 존재한다면 진행 방향으로 한칸 이동해 준 뒤 맵과 구조체에 다음 좌표로 갱신시켜 준다.
11. 만약 범위가 벗어났다면 맵에서 제거해 주고 원자의 life를 0으로 만든 뒤 원자의 개수 cnt를 줄여준다.
12. 모든 이동 작업이 완료되었다면, 해당 맵 좌표에 원자의 개수를 검사하고 2개 이상이라면 소멸 작업을 해준다.
13. pair 타입 set pos를 초기화 해주고, 다시 각 원자를 순회해 준다. 이때도 역시 life가 0이라면 continue 처리
14. 만약 맵상 현재 위치의 값이 2이상이라면 해당 좌표를 pos에 전달해 주고, 현재 원자가 가진 에너지를 ans에 더해준다.
15. 추가로 atom의 life를 0으로 처리해 주고 cnt를 1 줄여준다. 이 작업을 모든 원자에 진행해 주면 된다.
16. 소멸 작업이 완료되면 pos에 저장된 좌표를 순회하며 맵에서 해당 좌표를 0으로 만들어 준다.
17. 시뮬레이션이 완료된 후 ans 변수를 출력해 주면 된다.

 

참고 사항

2차원 좌표 문제이므로 x가 열 y가 행으로 주어진다. 입력 후 변수 배정과 방향배열 세팅에 신중해야 한다.

 

정답 코드

#include<iostream>
#include<vector>
#include<cstring>
#include<set>

using namespace std;
int tc, n, cnt, ans;
int lst[4001][4001];

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

struct Atom {
	int x, y, dir, e, life;
};

struct Pos {
	int x, y;
};

vector<Atom> atoms;

void init() {
	cnt = 0;
	ans = 0;
	atoms.clear();
	memset(lst, 0, sizeof(lst));
}

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y, dir, e; cin >> y >> x >> dir >> e;
		x = (x + 1000) * 2;
		y = (y + 1000) * 2;
		atoms.push_back({ x, y, dir, e, 1 });
		lst[x][y] = 1;
		cnt++;
	}
}

void simulation() {
	while (cnt > 0) {
		for (Atom& atom : atoms) {
			if (!atom.life) continue;
			int cx = atom.x, cy = atom.y, cd = atom.dir;
			int nx = cx + dx[cd], ny = cy + dy[cd];
			if (0 <= nx && nx <= 4000 && 0 <= ny && ny <= 4000) {
				lst[nx][ny] += 1;
				lst[cx][cy] -= 1;
				atom.x = nx, atom.y = ny;
			}
			else {
				lst[cx][cy] -= 1;
				atom.life = 0;
				cnt--;
			}
		}
		set<pair<int, int>> pos;
		for (Atom& atom : atoms) {
			if (!atom.life) continue;
			int cx = atom.x, cy = atom.y, ce = atom.e;
			if (lst[cx][cy] > 1) {
				pos.insert({ cx, cy });
				ans += ce;
				atom.life = 0;
				cnt--;
			}
		}
		for (pair<int, int> map : pos) lst[map.first][map.second] = 0;
	}
}

int main() {
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		init();
		input();
		simulation();
		cout << "#" << t << " " << ans << "\n";
	}
}