관리 메뉴

KoreanFoodie's Study

SW 역량테스트 - [백준] 낚시왕 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [백준] 낚시왕 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 10. 15. 23:48


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

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

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

 


문제 링크 : www.acmicpc.net/problem/17143

해답 코드 : 

 

#include <iostream>
#include <vector>

using namespace std;

typedef struct shark {

	int s; // speed
	int d; // direction
	int z; // size

}shark;

typedef struct pos_s {

	int r; // row
	int c; // col
	int s; // speed
	int d; // direction
	int z; // size

}pos_s;

int dR[4] = {-1, 1, 0, 0};
int dC[4] = {0, 0, 1, -1};


int M, N, K;

vector<shark> map[100][100];

// store moving sharks before update
vector<pos_s> moving;

// store caught shark
vector<shark> caught;

bool isRange(int row, int col) {
	if (row < 0 || row >= M || col < 0 || col >= N) {
		return false;
	} return true;
}

// return opposite direction
int op_dir(int x) {
	if (x == 0) return 1;
	else if (x == 1) return 0;
	else if (x == 2) return 3;
	else return 2;
}

void catch_shark(int king) {

	shark t_shark;

	for (int i = 0; i < M; i++) {
		
		if (!map[i][king].empty()) {
			t_shark = map[i][king][0];
			map[i][king].clear();
			caught.push_back(t_shark);
			break;
		}
	}

}

// move shark recursively
pos_s move_single(int row, int col, shark my) {

	// terminator, moved amount of 's'
	pos_s t_pos;

	int n_r = row;
	int n_c = col;

	// simplify speed value
	int cnt;

	if (my.d == 0 || my.d == 1) {
		cnt = my.s % ((M - 1) * 2);
	}
	else {
		cnt = my.s % ((N - 1) * 2);
	}


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

		n_r += dR[my.d];
		n_c += dC[my.d];

		// if out of range, reverse direction
		if (!isRange(n_r, n_c)) {
			my.d = op_dir(my.d);
			n_r = n_r + dR[my.d] * 2;
			n_c = n_c + dC[my.d] * 2;
		}
	}

	t_pos = { n_r, n_c, my.s, my.d, my.z };
	return t_pos;
}

shark resolve(vector<shark> clash) {
	
	int max_z = 0;
	shark t_shark = clash[0];

	for (int i = 0; i < clash.size(); i++) {
		if (max_z < clash[i].z) {
			t_shark = clash[i];
			max_z = clash[i].z;
		}
	}

	return t_shark;
	
}

void move_shark() {

	// clear moving shark vector
	moving.clear();
	
	pos_s t_pos;
	shark t_shark;

	// add moved shark to 'moving' vector
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (!map[i][j].empty()) {
				t_pos = move_single(i, j, map[i][j][0]);
				map[i][j].pop_back();
				moving.push_back(t_pos);
			}
		}
	}

	// update map[][] with moving
	for (int i = 0; i < moving.size(); i++) {
		t_pos = moving[i];
		t_shark = {t_pos.s, t_pos.d, t_pos.z};
		map[t_pos.r][t_pos.c].push_back(t_shark);

	}

	// if more than 1 shark is in the same cell, merge
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j].size() > 1) {
				t_shark = resolve(map[i][j]);
				map[i][j].clear();
				map[i][j].push_back(t_shark);
			}
		}
	}

}


void simulation() {

	// king move to right
	for (int king = 0; king < N; king++) {

		catch_shark(king);

		move_shark();

	}


}


int main() {

	cin >> M >> N >> K;

	shark t_shark;

	int t_r, t_c, t_s, t_d, t_z;
	int ans = 0;

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

		cin >> t_r >> t_c >> t_s >> t_d >> t_z;
		t_shark = {t_s, t_d-1, t_z};
		map[t_r - 1][t_c - 1].push_back(t_shark);

	}

	simulation();

	for (int i = 0; i < caught.size(); i++) {
		ans += caught[i].z;
	}

	cout << ans << endl;

}

 

 

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

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

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

 
0 Comments
댓글쓰기 폼