[백준 17143: 낚시왕] (C++)

삼성 SW 역량 테스트 기출 문제

https://www.acmicpc.net/workbook/view/1152

ㄴ낚시왕

           https://www.acmicpc.net/problem/17143

 

 

 

l 문제

 

1. 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다.  격자판의 각 칸은 (r, c)로 나타낼 수 있다. ( R, C )는 가장 오른쪽 아래 칸

2. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

3. 매 초 마다 다음 순서대로 일이 일이 일어난다.

 

 

l 순서

 

1. 낚시왕이 오른쪽으로 한 칸 이동한다 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다.

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.

3. 상어가 이동한다. 상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계인 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

4. 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

5. 낚시왕이 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

 

 

l 입력

 

첫째 줄에 격자판의 크기 R, C와 상어의 수 M (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z 로 이루어져 있다. (r, c)는 상어의 위치 s는 속력 d는 이동 방향 ( 1 : 위, 2 : 아래, 3 : 오른쪽, 4 : 왼쪽 ) z는 크기이다. (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

 

l 출력

 

낚시왕이 잡은 상어 크기의 합을 출력한다.

 

 

l 풀이

 

순서에 따라 시뮬레이션 하면 된다.

int shark_pos [R][C]; vector<상어 정보> shark_info; 시뮬레이션 함수 {   1. 낚시왕 이동   2. 가장 가까운 상어 잡기   3. 상어 이동   4. 같은 칸에 위치한 상어 처리 }

속도 s가 최대 1000인 상어들을 모든 과정에서 1칸/초 씩 이동 시키려고 하면 시간초과에 걸린다.

시간 단축 아이디어 상어가 이동하다가 제자리에 오는 경우가 생긴다. d = 1, 2 (상, 하) 일 때 (R-1)*2 회 이동하면 제자리로 온다. d = 3, 4 (좌, 우) 일 때 (C-1)*2 회 이동하면 제자리로 온다. 상어 정보를 입력 받을때 다음과 같이 속도를 줄여줄 수 있다. if (d <= 2) s %= (2 * R - 2); else           s %= (2 * C - 2);

상어 방향 회전 상어의 위치가 경계선(r = 1 또는 R / c = 1 또는 C)에 대가리를 박는 순간 바로 방향을 반대로 돌려주면 된다. d = 1 에서 3,1 -> 2,1 -> 1, 1 되는 순간 바로 d = 2로 바꿔줌

상어 잡기 / 같은 칸 처리 shark_pos 가장 가까운 상어를 잡을 때 배열을 이용하여 접근 시간 단축 shark_pos [ 1 ~ R ][ 낚시왕 위치 ] 중에 가장 가까운 상어 잡는다. 상어를 잡고나면 안의 데이터는 필요 없다. 따라서 -1로 초기화 해주고 상어를 이동시키는 과정에서 변경된 상어 위치를 기록한다. 기록하다가 칸에 이미 상어가 있다면 크기 z 를 비교해서 제거한다. 굳이 배열 2개를 써서 스왑해줄 필요가 없다는 것이다.

상어 제거 vector에서 상어를 매번 제거하는 거은 비효율적이다. 상어의 생존 상태를 상어 정보 구조체에 bool 값으로 넣거나 따로 외부 배열로 관리하여 죽은 상어는 잡지도, 이동시키지도 않도록 한다.

 

 

l  코드

 

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

int R, C, m, sum;
int dx[] = { -1, 1,0, 0 };
int dy[] = { 0, 0, 1,-1 };

struct fish
{
	int r, c, s, d, z;
	bool dead;

	void init()
	{
		if (d <= 2) s %= (2 * R - 2);
		else	    s %= (2 * C - 2);
		dead = false, --d;
	}

	void move()
	{
		for (int i = 0; i < s; ++i)
		{
			if      (d == 0 && r == 1) d = 1;
			else if (d == 1 && r == R) d = 0;
			else if (d == 2 && c == C) d = 3;
			else if (d == 3 && c == 1) d = 2;

			r += dx[d];
			c += dy[d];
		}
	}
} s;

vector<fish> shark_info;
int shark_pos[101][101];

int main()
{
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> R >> C >> m;
	shark_info.resize(m);
	memset(shark_pos, -1, sizeof(shark_pos));

	register int i, j, k;
	for (i = 0; i < m; ++i)
	{
		cin >> s.r >> s.c >> s.s >> s.d >> s.z;
		s.init();
		shark_info[i] = s;
		shark_pos[s.r][s.c] = i;
	}
	if (m == 0)
	{
		cout << 0;
		return 0;
	}
	// 1. 낚시왕 이동
	for (i = 1; i <= C; ++i)
	{
		// 2. 가장 가까운 상어 잡기
		for (j = 1; j <= R; ++j)
		{
			const int &idx = shark_pos[j][i];
			if (idx != -1 && shark_info[idx].dead == false)
			{
				sum += shark_info[idx].z;
				shark_info[idx].dead = true;
				break;
			}
		}
        
		// 위치 테이블은 낚시왕이 잡을 때만 사용함 ( 초기화 )
		memset(shark_pos, -1, sizeof(shark_pos));

		// 3. 상어 이동
		for (k = 0; k < m; ++k)
		{
			fish &s = shark_info[k];
			if (s.dead) continue;

			s.move();
            
			// cur_idx 가 -1이면 빈 곳
			int &cur_idx = shark_pos[s.r][s.c];
			if (cur_idx == -1) cur_idx = k;
			else
			{
				// 4. 같은 칸에 두 상어 처리
				if (shark_info[cur_idx].z < s.z)
				{
					shark_info[cur_idx].dead = true;
					cur_idx = k;
				}
				else shark_info[k].dead = true;
			}
		}
	}
	cout << sum;
	return 0;
}