관리 메뉴

KoreanFoodie's Study

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

Data Structures, Algorithm/SW 역량테스트

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

hashnut 2020. 10. 16. 17:49


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

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

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

 


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

해답 코드 : 

 

#include <iostream>
#include <vector>

using namespace std;

typedef struct shark {

	int row;
	int col;
	int num;
	int dir;
	int prior[4][4];
	int alive;

} shark;

typedef struct tile {
	
	int sh_num;
	int smell;
	int sm_num;

}tile;

int N, M, K;
 
shark sharks[400];
tile map[20][20];

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

bool isRange(int r, int c) {
	if (r < 0 || r >= N || c < 0 || c >= N) {
		return false;
	}
	else return true;
}

// check only zero shark is alive
bool check_zero() {

	for (int i = 1; i < M; i++) {
		if (sharks[i].alive == 1) {
			return false;
		}
	}

	return true;
}

void perfume() {

	shark c_sh;
	int c_r, c_c;


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

		c_sh = sharks[i];

		if (c_sh.alive == 1) {
			c_r = c_sh.row;
			c_c = c_sh.col;

			map[c_r][c_c].smell = K;
			map[c_r][c_c].sm_num = i;

		}
	}
}

void tick() {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j].smell > 0) {
				map[i][j].smell--;
			}
		}
	}
}

void shark_move() {

	shark c_sh;
	int c_r, c_c;
	int n_r, n_c;
	int c_d, n_d;
	bool no_empty = true;
	tile n_tile;

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

		c_sh = sharks[sh];

		if (c_sh.alive == 0) continue;

		c_d = c_sh.dir;
		c_r = c_sh.row;
		c_c = c_sh.col;
		
		no_empty = true;

		// check empty tile
		for (int i = 0; i < 4; i++) {
			
			n_d = c_sh.prior[c_d][i];

			n_r = c_r + dR[n_d];
			n_c = c_c + dC[n_d];

			// empty tile : care if there is a shark
			if (isRange(n_r, n_c) && map[n_r][n_c].smell == 0) {
				
				no_empty = false;

				// if another shark is already there
				if (map[n_r][n_c].sh_num != -1) {

					int conf_num = map[n_r][n_c].sh_num;

					// if small, eat
					if (c_sh.num < map[n_r][n_c].sh_num) {
						sharks[conf_num].alive = 0;
						//map[n_r][n_c].sh_num = c_sh.num;
					}


					// if large, be eaten (Do not move)
					else if (c_sh.num > map[n_r][n_c].sh_num) {
						map[c_r][c_c].sh_num = -1;
						sharks[sh].alive = 0;
						break;
					}

				}

				// if no shark is there, just move (also move when he wins)

				// emptying
				map[c_r][c_c].sh_num = -1;

				// update
				map[n_r][n_c].sh_num = c_sh.num;
				sharks[sh].row = n_r;
				sharks[sh].col = n_c;
				sharks[sh].dir = n_d;
				break;

			}
			

		}


		// check tiles with his smell
		if (no_empty) {

			for (int i = 0; i < 4; i++) {
				n_d = c_sh.prior[c_d][i];

				n_r = c_r + dR[n_d];
				n_c = c_c + dC[n_d];

				n_tile = map[n_r][n_c];

				if (isRange(n_r, n_c) && n_tile.smell > 0 && n_tile.sm_num == c_sh.num) {

					// emptying
					map[c_r][c_c].sh_num = -1;

					// update
					map[n_r][n_c].sh_num = c_sh.num;
					sharks[sh].row = n_r;
					sharks[sh].col = n_c;
					sharks[sh].dir = n_d;

					break;

				}
			}

		}


	}


}




void simulation() {

	perfume();
	shark_move();
	tick();

}


int main() {

	cin >> N >> M >> K;

	int t_num, t_d, t_p;
	int time;


	// map, shark initialization
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> t_num;
			if (t_num > 0) {
				sharks[t_num - 1] = {i, j, t_num-1, -1, };
				sharks[t_num - 1].alive = 1;
			}
			map[i][j] = {t_num-1, 0, 0};

		}
	}

	// direction init for sharks
	for (int i = 0; i < M; i++) {
		cin >> t_d;
		sharks[i].dir = t_d - 1;
	}

	// prior init for sharks
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> t_p;
				sharks[i].prior[j][k] = t_p - 1;
			}
		}
	}


	for (time = 1; time <= 1000; time++) {
		simulation();
		if (check_zero()) {
			break;
		}
	}

	if (time > 1000) time = -1;

	cout << time << endl;

}

 

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

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

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

 
0 Comments
댓글쓰기 폼