boj, 백준 ) 17143 낚시왕 ( C / C++ )

1. 문제 링크

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

17143번: 낚시왕

2. 문제 개요

R*C인 격자판의 상어를 한차례씩 낚는 프로그램

단, 상어는 개별의 속도 크기를 갖고있으며 매 턴 이동한다.

 

3. 문제 힌트!! -> 힌트보고 한번 더 풀어보세요

상어의 이동이 일정 크기가 넘어가면 반복된다.

 

4. 문제 풀이

상어 구조체를 만들어 입력 변수와 함께 죽었는지 아닌지를 구별하는 bool 변수를 1개 추가한다.

그리고 한 지점에 2마리의 상어가 있을때의 경우를 빨리 처리하기위해 별도의 맵을 선언한다.

 

//사냥

입력변수들을 입력받고 맵의 가로길이만큼 반복한다.

첫번째 열에서 0행부터 마지막행까지 내려가면서 상어가 존재하는지 맵에서 확인하고, 있다면 그 상어의 죽음을 표시하는 bool변수를 true로 나타내고 결과값에 누적시킨다.

 

//이동

이동에서는 모든 상어가 각자의 방향과 크기만큼 이동하게된다.

하지만 여기서 크기가 매우 크다는것에 주의를 해야한다. 정말 1개1개씩 움직이면 시간초과가 난다.

교정된 상어의 이동크기(s) = s % (2 * y - 2)와 같다고 할 수 있다. (노트에 한번 그려보는것 추천)

가로로 이동하는 상어라면 y자리에 x가 들어가야함.

 

//배치

이동한 상어의 데이터를 바탕으로 맵에 다시 그린다.

맵을 우선 초기화 하고, 1번째 상어부터 m번째 상어까지 맵에 그리는데, 맵의 해당 좌표에 값이 0 이라면 상어가

존재하지 않는다는 뜻이고 그냥 배치하면된다.

하지만 값이 0 이아니고 예를들어 3이라는 숫자가 있다면, 3번째 상어와 중복되는 위치에 자리하게 되는것이고 

크기가 크고 작음을 따져봐야한다.

 

이러한 과정을 반복하고 결과값을 출력하면 정답을 알 수 있다.

 

5. 코드

#include <cstdio>
int map[101][101];

struct SHARK{
	int y, x;
	int s, d, z;
	bool isdead;
}shark[10001];

const int dx[] = { 0,0,0,1,-1 };
const int dy[] = { 0,-1,1,0,0 };

int main(void)
{
	int ret = 0;
	int y, x, m;
	scanf("%d %d %d", &y, &x, &m);

	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d %d %d %d",
			&shark[i].y, &shark[i].x, &shark[i].s, &shark[i].d, &shark[i].z);
		map[shark[i].y][shark[i].x] = i;
	}
	
	
	for (int t = 1; t <= x; t++)
	{
		//사냥
		for (int k = 1; k <= y; k++)
		{
			if (map[k][t] != 0)
			{
				//v번째 상어가 있다면,
				shark[map[k][t]].x = -1;
				shark[map[k][t]].y = -1;
				shark[map[k][t]].isdead = true;
				ret += shark[map[k][t]].z;
				map[k][t] = 0;
				break;
			}
		}


		//이동
		for (int i = 1; i <= m; i++)
		{
			if (shark[i].isdead) continue;

			if (shark[i].d == 1 || shark[i].d == 2)
			{
				shark[i].s = shark[i].s % (2 * y - 2);

				int ny = shark[i].y + shark[i].s*dy[shark[i].d];

				while (ny <1 || ny >y)
				{
					if (ny > y)
					{
						ny = 2 * y - ny;
						shark[i].d = 1;
					}
					else if (ny < 1)
					{
						ny = (1 - ny) + 1;
						shark[i].d = 2;
					}
				}
				shark[i].y = ny;

			}
			else
			{
				shark[i].s = shark[i].s % (2 * x - 2);

				int nx = shark[i].x + shark[i].s*dx[shark[i].d];

				while (nx <1 || nx >x)
				{
					if (nx > x)
					{
						nx = 2 * x - nx;
						shark[i].d = 4;
					}
					else if (nx < 1)
					{
						nx = (1 - nx) + 1;
						shark[i].d = 3;
					}
				}
				shark[i].x = nx;

			}
		}

		for (int i = 1; i <= y; i++)
			for (int j = 1; j <= x; j++)
				map[i][j] = 0;

		for (int i = 1; i <= m; i++)
		{
			if (!shark[i].isdead)
			{
				if (map[shark[i].y][shark[i].x] == 0)
					map[shark[i].y][shark[i].x] = i;
				else
				{
					if (shark[map[shark[i].y][shark[i].x]].z < shark[i].z)
					{
						//내가 더크면,
						shark[map[shark[i].y][shark[i].x]].x = -1;
						shark[map[shark[i].y][shark[i].x]].y = -1;
						shark[map[shark[i].y][shark[i].x]].isdead = true;
						map[shark[i].y][shark[i].x] = i;
					}
					else
					{
						//내가 더 작으면
						shark[i].x = shark[i].y = -1;
						shark[i].isdead = true;
					}
				}
			}
		}
	}

	printf("%d", ret);
	


	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~