KoreanFoodie's Study

SW 역량테스트 - [모의 SW 역량테스트] 원자 소멸 시뮬레이션 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [모의 SW 역량테스트] 원자 소멸 시뮬레이션 문제 풀이/해답/코드 (C++ / JAVA)

GoldGiver 2020. 9. 29. 11:48


SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 


문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo

해답 코드 : 

 

#include <iostream>
#include <vector>
#include <math.h>


using namespace std;

typedef struct atom {
	int x;
	int y;
	int dir;
	int energy;
}atom;

typedef struct crush {

	int in1; // index of atoms[1001]
	int in2;
	int min_time_2; // sort vector<minA> with min_time
	// use this to remove pre-vanished atoms

}crush;

int K;
atom atoms [1001];
bool boom[1001];
int atoms_min[1001];

vector<crush> del_atoms;

int e_sum;

int dX[4] = {0, 0, -1, 1};
int dY[4] = {1, -1, 0, 0};


int main(int argc, char** argv)
{
	int test_case;
	int T;
	/*
	   아래의 freopen 함수는 input.txt 를 read only 형식으로 연 후,
	   앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
	   //여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
	   freopen 함수를 이용하면 이후 cin 을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
	   따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 함수를 사용하셔도 좋습니다.
	   freopen 함수를 사용하기 위해서는 #include <cstdio>, 혹은 #include <stdio.h> 가 필요합니다.
	   단, 채점을 위해 코드를 제출하실 때에는 반드시 freopen 함수를 지우거나 주석 처리 하셔야 합니다.
	*/
	//FILE *fp;
	//freopen_s(&fp, "sample_input.txt", "r", stdin);

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> K;

		fill(atoms_min, atoms_min + 1000, 8192);
		fill(boom, boom + 1000, false);

		e_sum = 0;

		int i_r, i_c, i_d, i_e;

		for (int i = 0; i < K; i++) {
			cin >> i_r >> i_c >> i_d >> i_e;
			atoms[i] = { i_r, i_c, i_d, i_e };
		}

		atom atom_i;
		atom atom_j;
		crush i_j;

		int dist_r;
		int dist_c;

		// actually it is doubled

		vector<crush>::iterator iter;
		bool push_back;

		for (int i = 0; i < K - 1; i++) {

			atom_i = atoms[i];
			

			for (int j = i+1; j < K; j++) {

				atom_j = atoms[j];
				push_back = true;

				// same direction, continue;
				if (atom_i.dir == atom_j.dir) continue;

				if (atom_i.x == atom_j.x) {

					if (((atom_i.y < atom_j.y) && (atom_i.dir == 0 && atom_j.dir == 1)) ||
						((atom_i.y > atom_j.y) && (atom_i.dir == 1 && atom_j.dir == 0))) {

						dist_c = abs(atom_i.y - atom_j.y);

						i_j = {i, j, dist_c};

						if (atoms_min[i] > dist_c) atoms_min[i] = dist_c;
						if (atoms_min[j] > dist_c) atoms_min[j] = dist_c;

						if (del_atoms.empty()) {
							del_atoms.push_back(i_j);
							continue;
						}


						for (iter = del_atoms.begin(); iter != del_atoms.end(); iter++) {
							if ((*iter).min_time_2 < dist_c) {
								continue;
							}
							else {
								del_atoms.insert(iter, i_j);
								push_back = false;
								break;
							}
						
						}

						if (push_back) del_atoms.push_back(i_j);
						

					}
					
				}
				else if (atom_i.y == atom_j.y) {

					if (((atom_i.x < atom_j.x) && (atom_i.dir == 3 && atom_j.dir == 2)) ||
						((atom_i.x > atom_j.x) && (atom_i.dir == 2 && atom_j.dir == 3))) {

						dist_r = abs(atom_i.x - atom_j.x);

						i_j = { i, j, dist_r };

						if (atoms_min[i] > dist_r) atoms_min[i] = dist_r;
						if (atoms_min[j] > dist_r) atoms_min[j] = dist_r;

						if (del_atoms.empty()) {
							del_atoms.push_back(i_j);
							continue;
						}

						for (iter = del_atoms.begin(); iter != del_atoms.end(); iter++) {
							if ((*iter).min_time_2 < dist_r) {
								continue;
							}
							else {
								del_atoms.insert(iter, i_j);
								push_back = false;
								break;
							}

						}

						if (push_back) del_atoms.push_back(i_j);
					}

				} // x, y coordinates are different
				else {

					dist_r = abs(atom_i.x - atom_j.x);
					dist_c = abs(atom_i.y - atom_j.y);

					if (dist_r != dist_c) continue;

					if ( ( ( (atom_i.x + dist_r * dX[atom_i.dir]) == atom_j.x) &&
						( (atom_j.y + dist_c * dY[atom_j.dir]) == atom_i.y) ) ||

						(((atom_i.y + dist_c * dY[atom_i.dir]) == atom_j.y) &&
							((atom_j.x + dist_r * dX[atom_j.dir]) == atom_i.x)))
					{

						i_j = { i, j, dist_r * 2 };

						if (atoms_min[i] > dist_r * 2) atoms_min[i] = dist_r * 2;
						if (atoms_min[j] > dist_r * 2) atoms_min[j] = dist_r * 2;

						if (del_atoms.empty()) {
							del_atoms.push_back(i_j);
							continue;
						}

						for (iter = del_atoms.begin(); iter != del_atoms.end(); iter++) {
							if ((*iter).min_time_2 < dist_r * 2) {
								continue;
							}
							else {
								del_atoms.insert(iter, i_j);
								push_back = false;
								break;
							}

						}
						if (push_back) del_atoms.push_back(i_j);
					}

				}

			}
		}

		// int temp_t;
		// if (!del_atoms.empty()) temp_t = del_atoms[0].min_time_2;

		for (int i = 0; i < del_atoms.size(); i++) {
			
			// both are boomed
			if (boom[del_atoms[i].in1] && boom[del_atoms[i].in2]) {
				continue;
			}
			// if only one of them is boomed
			else if ( (!boom[del_atoms[i].in1] && boom[del_atoms[i].in2]) || 
				      (boom[del_atoms[i].in1] && !boom[del_atoms[i].in2])) {

				  	if (atoms_min[del_atoms[i].in1] == del_atoms[i].min_time_2 &&
						atoms_min[del_atoms[i].in2] == del_atoms[i].min_time_2) {
						e_sum += atoms[del_atoms[i].in1].energy;
						e_sum += atoms[del_atoms[i].in2].energy;
						atoms[del_atoms[i].in1].energy = 0;
						atoms[del_atoms[i].in2].energy = 0;
						boom[del_atoms[i].in1] = true;
						boom[del_atoms[i].in2] = true;
					}

			     }
			
			else {
				e_sum += atoms[del_atoms[i].in1].energy;
				e_sum += atoms[del_atoms[i].in2].energy;
				atoms[del_atoms[i].in1].energy = 0;
				atoms[del_atoms[i].in2].energy = 0;
				boom[del_atoms[i].in1] = true;
				boom[del_atoms[i].in2] = true;
			}

		}
		
		// clear del_atoms
		del_atoms.clear();
		

		cout << "#" << test_case << " " << e_sum << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

Comments