백준 17143 - 낚시왕(C++)

문제 링크입니다 https://www.acmicpc.net/problem/17143

17143번: 낚시왕

삼성 SW 역량 테스트 기출문제였습니다!

문제 조건

 

출력 예시

 

문제 접근 방법

1. 상어의 정보를 vector에 저장한다.

2. 먼저 낚시꾼이 상어를 잡는다. -> 이때 잡은 상어는 잡았다는 표시를 한다.

3. 상어를 움직인다. -> 이때 speed만큼 전부 움직인다면 시간초과가 된다. 따라서 움직이는 횟수를 줄여야한다.

                          -> 한마리 상어를 전부 움직였을때, 그 자리에 상어가 있다면 크기를 비교해 상어를 없앤다.

4. 2번과 3번을 C만큼 반복한다.

 

문제 접근 방법 3-1번 움직임에 대한 부가 설명

최악의 경우에 상어가 10000마리, 상어의 speed가 전부 1000이라고 할때, 한번 상어가 전부 움직일 때마다 10^8의 연산이 필요합니다. 이때 무조건 시간 초과가 됩니다. 따라서 움직임을 줄이는 방법이 필요합니다.

(1,1)	(1,2)	(1,3)	(1,4)	(1,5)	(1,6)	(1,7)
(2,1)	(2,2)	(2,3)	(2,4)	(2,5)	(2,6)	(2,7)
(3,1)	(3,2)	(3,3)	(3,4)	(3,5)	(3,6)	(3,7)

위와 같은 좌표가 있다고 했을 때,

(2,5)에서 9번 오른쪽으로 움직이면 어떻게 될까? -> (2,2)로 도착한다.

(2,5)에서 4번 오른쪽으로 움직였을때는? -> (2,5)로 돌아온다.

(2,5)에서 12번 오른쪽으로 움직였을때는? -> (2,5)로 돌아온다.

따라서 R 또는 C범위 만큼 움직일 때, (R-1)*2 또는 (C-1)*2의 나머지 만큼만 움직이면 전체를 움직인 것과 같은 효과를 볼 수 있다!

 

 

문제 접근 방법 - 2번

void capture_shark(int y) {
	for (int i = 1; i <= R; i++) {
		if (num_shark[i][y] > 0) {
			get_shark += shark[num_shark[i][y]-1].size_;
			out_shark[num_shark[i][y]-1] = true;
			break;
		}
	}
}

해당 열 번호에서 1~R까지 행을 살펴봅니다. 위에서부터 봤을 때, 해당 좌표에 상어가 있다면 상어를 잡은 후에 그 상어를 잡았다는 표시를 합니다.

num_shark[][] -> 해당 좌표에 X번 상어가 존재한다

out_shark[] -> 해당 번호의 상어가 잡혔는지의 여부를 알려준다. -> 계속 나오니깐 기억해주세요

 

 

문제 접근 방법 - 3번

void move(int num, int x, int y, int speed, int dir) {
	if (dir == 1 || dir == 2) {
		int rotate = (R - 1) * 2;
		if (speed >= rotate) speed = speed % rotate;
	}
	else {
		int rotate = (C - 1) * 2;
		if (speed >= rotate) speed = speed % rotate;
	}
	while (1) {
		if (speed == 0) break;
		if (dir == 1) {
			if (x == 1) dir = 2;
		}
		else if (dir == 2) {
			if (x == R) dir = 1;
		}
		else if (dir == 3) {
			if (y == C) dir = 4;
		}
		else if (dir == 4) {
			if (y == 1) dir = 3;
		}
		x += dx[dir-1];
		y += dy[dir-1];
		speed--;
	}
	shark[num].r = x;
	shark[num].c = y;
	shark[num].dir = dir;
	if (num_shark[x][y] != 0) {
		if (shark[num_shark[x][y] - 1].size_ < shark[num].size_) {
			out_shark[num_shark[x][y] - 1] = true;
			num_shark[x][y] = num + 1;
		}
		else {
			out_shark[num] = true;
		}
	}
	else {
		num_shark[x][y] = num + 1;
	}
}

void move_shark() {
	for (int i = 0; i < M; i++) {
		if (!out_shark[i]) {
			int x = shark[i].r;
			int y = shark[i].c;
			int speed = shark[i].speed;
			int direction = shark[i].dir;
			int size_ = shark[i].size_;
			move(i,x, y, speed, direction);
		}
	}
}

해당 번호의 상어가 존재할 때, 백터에 담아둔 정보를 통해서 상어를 움직입니다.

1. 위, 아래로 움직일 때 -> (R-1)*2의 나머지 만큼만 움직입니다.

2. 왼, 오른쪽으로 움직일 때 -> (C-1)*2의 나머지 만큼만 움직입니다.

상어가 도착한 좌표에 이전에 도착했던 상어가 존재한다면 -> 크기를 비교해 큰 상어만 남깁니다!

 

자세한 것은 코드를 참고해주세요!

 

#define CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define MAX 100001
using namespace std;

int R, C, M;
int map[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };
int get_shark;
typedef struct sh {
	int r;
	int c;
	int speed;
	int dir;
	int size_;
}sh;
bool out_shark[10001];
vector<sh> shark;
int num_shark[101][101];

void capture_shark(int y) {
	for (int i = 1; i <= R; i++) {
		if (num_shark[i][y] > 0) {
			get_shark += shark[num_shark[i][y]-1].size_;
			//cout << num_shark[i][y] << " ";
			out_shark[num_shark[i][y]-1] = true;
			break;
		}
	}
}


void move(int num, int x, int y, int speed, int dir) {
	if (dir == 1 || dir == 2) {
		int rotate = (R - 1) * 2;
		if (speed >= rotate) speed = speed % rotate;
	}
	else {
		int rotate = (C - 1) * 2;
		if (speed >= rotate) speed = speed % rotate;
	}
	while (1) {
		if (speed == 0) break;
		if (dir == 1) {
			if (x == 1) dir = 2;
		}
		else if (dir == 2) {
			if (x == R) dir = 1;
		}
		else if (dir == 3) {
			if (y == C) dir = 4;
		}
		else if (dir == 4) {
			if (y == 1) dir = 3;
		}
		x += dx[dir-1];
		y += dy[dir-1];
		speed--;
	}
	//cout << x << " " << y << " " << " " << num + 1 << "\n";
	shark[num].r = x;
	shark[num].c = y;
	shark[num].dir = dir;
	if (num_shark[x][y] != 0) {
		if (shark[num_shark[x][y] - 1].size_ < shark[num].size_) {
			out_shark[num_shark[x][y] - 1] = true;
			num_shark[x][y] = num + 1;
		}
		else {
			out_shark[num] = true;
		}
	}
	else {
		num_shark[x][y] = num + 1;
	}
}

void move_shark() {
	for (int i = 0; i < M; i++) {
		if (!out_shark[i]) {
			int x = shark[i].r;
			int y = shark[i].c;
			int speed = shark[i].speed;
			int direction = shark[i].dir;
			int size_ = shark[i].size_;
			move(i,x, y, speed, direction);
		}
	}
}

void solve() {
	for (int i = 1; i <= C; i++) {
		capture_shark(i);
		memset(num_shark, 0, sizeof(num_shark));
		move_shark();
	}
	cout << get_shark;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> R >> C >> M;
	for (int i = 1; i <= M; i++) {
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;
		shark.push_back({ r,c,s,d,z });
		num_shark[r][c] = i;
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!