알고리즘 문제 풀어보자. 은하 전쟁!

* 문제: 은하 전쟁

은하계의 행성들이 전쟁을 벌이고 있다. 이 행성들은 너무 멀어서 아주 빠른 미사일로만 서로를 공격한다. 미사일은 100% 명중하며 기반시설에 일정한 피해를 입힌다. 기반시설 N 개일 때 단위시간당 N/10 개의 미사일을 생성한다. 10보다 작은 규모에서는 미사일이 생성되지 않는다. 미사일은 단위시간당 단위거리르 가며 N개의 미사일은 N개의 기반시설을 파괴한다. 기반시설은 복구되지 않으며 기반시설이 0이 되면 그 행성은 진다.

다음 데이터에는 각 행성의 위치와 초기 기반시설 규모가 적혀 있다. 모든 행성은 적대 관계이며, 가장 가까운 행성이 질 때까지 그 행성만 공격한다. 단, 공격자가 미리 상대가 질 것을 예상하고 목표를 수정하지는 않는다. 실제로 대상이 파괴될 때까지 공격을 계속한다.

전쟁 결과 마지막에 남는 별의 좌표를 적어라. (만약 살아남는 별이 없으면 '없음'이라고 적는다.)

* 위치, 시간, 규모 등은 모두 정수이다.
* 피격은 단위 시간 1이 흐른 뒤에 일어난다.
* 단위 시간 안에 일어날 수 있는 피격이 모두 적용된 다음 미사일을 발사한다.
* 행성 기반시설이 0이 되어도 날아가던 미사일은 계속 날아가 목표를 타격한다.
* 미사일이 모두 없어져야 전쟁이 끝난다.

-- 데이터 포맷 --
<별 위치 X> <별 위치 Y> <기반 시설 규모>
<별 위치 X> <별 위치 Y> <기반 시설 규모>
...

예)
0 10 100
10 0 200

의 답은 (10, 0)

---

* 풀어보기

#include <iostream> #include <vector> #include <math.h> using namespace std; int starNumber = 0; // 행성 수 vector<int> X; // 위치 X vector<int> Y; // 위치 Y vector<int> N; // 기반 시설 규모 vector<int> target; vector<int> missile; int missileSum = 0; void targetSet() { // 타겟 설정 target.clear(); // 모든 타겟 초기화 double distance, tempDistance; int tempTarget; // 타겟으로 지정 for (int j = 0; j < starNumber; j++) { distance = 0, tempDistance = 0, tempTarget = 0; for (int k = 0; k < starNumber; k++) { if(j != k){ // 자신과의 거리는 측정 피함 tempDistance = sqrt(pow(X[j] - X[k], 2) + pow(Y[j] - Y[k], 2)); // 거리 측정 if(distance == 0){ // 처음 비교되는 행성일 경우 바로 저장 distance = tempDistance; tempTarget = k; } else if(tempDistance < distance){ // 기존에 거리 쵯솟값과 비교 distance = tempDistance; tempTarget = k; } } } target.push_back(tempTarget); // 타겟을 저장 cout << "행성" << j+1 << " (" << X[j] << "," << Y[j] << ") N:" << N[j] << "-> target: 행성 " << tempTarget+1 << "(" << X[tempTarget] << "," <<Y[tempTarget] << ")" << endl; } // cout << "missileSum:" << missileSum << endl << endl; } int main() { cout << "행성의 숫자를 입력: "; cin >> starNumber; for (int i = 0; i < starNumber; i++) { int tempX = 0, tempY = 0, tempN = 0; cin >> tempX >> tempY >> tempN; X.push_back(tempX); Y.push_back(tempY); N.push_back(tempN); missile.push_back(tempN / 10); missileSum += tempN/10; } cout << endl; targetSet(); for (int k = 0; k < 100; k++){ if(starNumber==1 || starNumber==0 || missileSum==0) break; else { for (int j = 0; j < starNumber; j++) { // cout << "행성" << j+1 << "이 행성" << target[j]+1 << "을 " << missile[j] << "만큼 공격, " << N[target[j]] << "->"; N[target[j]] -= missile[j]; // 목표 공격 missileSum -= missile[j]; // 총 마사일 수 감소 missile[j] -= missile[j]; // 사용한 미사일 수 감소 // cout << N[target[j]] << ", missileSum:" << missileSum << endl; } for (int j2 = 0; j2 < starNumber; j2++){ if(N[j2]>=10){ missile[j2] += (N[j2]/10); // 미사일 증가 missileSum += (N[j2]/10); // 총 미사일 수 감소 } } for (int j3 = 0; j3< starNumber; j3++) { if(N[j3]<=0){ cout << "행성" << j3+1 << " (" << X[j3] << "," << Y[j3] << ") 파괴!!!" << endl << endl; if (--starNumber> 1){ X.erase(X.begin() + j3); Y.erase(Y.begin() + j3); N.erase(N.begin() + j3); missile.erase(missile.begin() + j3); target.erase(target.begin() + j3); targetSet(); } } } } } if(starNumber==1) cout << "Winner: " << X[0] << " " << Y[0] << endl; else if(starNumber==0) cout << "Winner: 없음" << endl; else{ cout << endl << "[생존 행성] 미사일 모두 사용!" << endl; for(int i=0; i < starNumber; i++){ cout << "(" << X[i] << "," << Y[i] << ") 남은 기반시설:" << N[i] << endl; } } return 0; }

---

* 실행 결과 1

행성의 숫자를 입력: 2
0 10 100
10 0 200

행성1 (0,10) N:100-> target: 행성 2(10,0)
행성2 (10,0) N:200-> target: 행성 1(0,10)
행성1 (0,10) 파괴!!!

Winner: 0 10

---

* 실행 결과 2

행성의 숫자를 입력: 3
0 10 100
10 0 200
3 5 300

행성1 (0,10) N:100-> target: 행성 3(3,5)
행성2 (10,0) N:200-> target: 행성 3(3,5)
행성3 (3,5) N:300-> target: 행성 1(0,10)
행성1 (0,10) 파괴!!!

행성1 (10,0) N:200-> target: 행성 2(3,5)
행성2 (3,5) N:198-> target: 행성 1(10,0)
행성2 (3,5) 파괴!!!

Winner: 10 0

---

* 실행 결과 3

행성의 숫자를 입력: 2
0 10 100
10 0 100

행성1 (0,10) N:100-> target: 행성 2(10,0)
행성2 (10,0) N:100-> target: 행성 1(0,10)

[생존 행성] 미사일 모두 사용!
(0,10) 남은 기반시설:9
(10,0) 남은 기반시설:9