KoreanFoodie's Study

SW 역량테스트 - [모의 SW 역량테스트] 미생물 격리 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [모의 SW 역량테스트] 미생물 격리 문제 풀이/해답/코드 (C++ / JAVA)

GoldGiver 2020. 9. 29. 11:44


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

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

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

 


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

해답 코드 : 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct micro {
	int row;
	int col;
	int num; // 미생물의 갯수
	int dir; // 상 하 좌 우 각각 0 1 2 3
	bool same;

} micro;


int N, M, K;
int org_sum;


// 상, 하, 좌, 우
int dR[4] = {-1, 1, 0, 0 };
int dC[4] = {0, 0, -1, 1};

// 가장자리에 있는지 체크
bool isEnd(int r, int c) {
	if (r == 0 || c == 0 || r == N - 1 || c == N - 1) {
		return true;
	}
	else return false;
}

// 반대 방향을 뱉어냄
int op_dir(int dir) {

	if (dir == 0) return 1;
	else if (dir == 1) return 0;
	else if (dir == 2) return 3;
	else return 2;

}

bool isZero(micro m) {
	if (m.num == 0) return true;
	else return false;
	//return !m.num;
}

bool isSame(micro m) {
	return m.same;
}


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 >> N >> M >> K;

		org_sum = 0;

		int i_c, i_r, i_n, i_d;
		micro temp;

		// 미생물 군집 벡터
		vector<micro> org;
		vector<micro> org_n; // for update & merge


		for (int i = 0; i < K; i++) {
			cin >> i_r >> i_c >> i_n >> i_d;
			
			temp.row = i_r;
			temp.col = i_c;
			temp.num = i_n;
			temp.dir = i_d - 1;
			temp.same = false;

			org.push_back(temp);

		}


		// temp row, col, number, dir, biggest 
		int t_c, t_r, t_n, t_d, t_b;

		for (int i = 0; i < M; i++) {

			// update the position
			// if is in the end, cut the number in half
			for (int i = 0; i < org.size(); i++) {
				t_d = org[i].dir;
				t_r = org[i].row + dR[t_d];
				t_c = org[i].col + dC[t_d];
				
				if (isEnd(t_r, t_c)) {

					org[i].num = org[i].num / 2;
					org[i].dir = op_dir(t_d);
				}

				org[i].row = t_r;
				org[i].col = t_c;

			}

			// delete whose num is 0
			org.erase(std::remove_if(org.begin(), org.end(), ::isZero), org.end());

			// merge, direction -> for the biggest
			// if same position, merge, otherwise, skip
			
			// new row, col, num, dir
			int n_r, n_c, n_n, n_d;
			int max_num, max_num_dir, num_sum;

			// clear the backup
			org_n.clear();

			while (!org.empty()) {

				// store index to be deleted
				//vector<int> del;
				
				temp = org[org.size() - 1];
				n_r = temp.row;
				n_c = temp.col;
				n_n = temp.num;
				n_d = temp.dir;
				
				max_num = n_n;
				max_num_dir = n_d;
				num_sum = n_n;

				org.pop_back();

				for (int i = 0; i < org.size(); i++) {
					
					if (org[i].row == n_r && org[i].col == n_c) {
						
						if (org[i].num > max_num) {
							max_num = org[i].num;
							max_num_dir = org[i].dir;
						}

						num_sum += org[i].num;
						org[i].same = true;
					}

				}

				// remove duplicates
				org.erase(std::remove_if(org.begin(), org.end(), ::isSame), org.end());

				// make new merged one
				micro new_m = {n_r, n_c, num_sum, max_num_dir, false};

				org_n.push_back(new_m);

			}

			// update org
			org.insert(org.begin(), org_n.begin(), org_n.end());

		}

		for (int i = 0; i < org.size(); i++) {
			org_sum += org[i].num;
		}

		
		cout << "#" << test_case << " " << org_sum << endl;
	}

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

 

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

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

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

 
Comments