백준 17143번: 낚시왕 (C++)

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

 

 

시뮬레이션, 구현 문제이다.

 

<전체적인 알고리즘>

1. 오른쪽으로 한 칸 이동한다.

2. 물고기를 잡는다.

    -물고기를 잡을때는 해당 열에서 밑으로 내려가면서 탐색을 하다가 상어를 만나면 지도에서 제거하고 sum에 더한다.

3. 1초동안 물고기들을 움직이게 한다.

    - 지도를 탐색하면서 상어가 있으면 상어들을 움직이게 해준다. 움직인 상어들을 tmp임시지도에 저장한다.

    - 임시 지도를 현실 지도로 복사한다. 

      (현실 지도를 순차탐색 하고 있기 때문에 이미 움직인 상어를 선택하지 않기 위해 임시지도 사용)

4. 1,2,3번을 n번 반복한다.

 

<주의할 점> (시간복잡도)

생각없이 그냥 속력1마다 이동하는 식으로 구현을 하면 시간초과가 나게 된다. 그 이유는 상어의 s속력의 범위가 1000이하이기 때문이다. 시간복잡도는 항상 최악의 경우를 고려하여야 한다. 예를 들어 물속이 100*100,, 상어의 속력들이 1000,, 거의 모든 공간에 상어가 존재하고, 상어들이 거의 서로 못잡아 먹는 조건이되면 (상어들이 움직여서 제자리로 돌아오게만 해도  못잡아먹음) 

공간 개수 * 상어 속력 * 사람이 움직이는 거리(가로 길이) = 100*100*1000*100 = 10억 이상의 연산이 발생한다.

일반적으로 1억번 연산하는데 1초로 생각을 해보면  가볍게 시간제한인 1초를 넘어가게 된다.

속력을 확 줄이는 방법이 있다. 아래 두 줄을 추가하는 것이다.

한 바퀴 돌아서 제자리로 돌아오는 경우는 가만히 있는 거랑 다를게 없으니 속력=(속력/제자리로 돌아오는데 걸리는 거리)를 해주자. 

 

**위와같이 코드를 추가해주면 통과를 한다. 하지만 실제로는 위와같이 해도 조금 위험하다. 만약 위에서 설명한 최악의 경우가 온다면 아슬아슬하다. 결론은 그냥 속력1마다 한칸씩 움직이는 것이 아니라 벽까지의 거리를 계산하여 한번에 계산해주면 완벽하다.

하지만 코드가 조금 지저분해 질 수 있기에 본인은 그냥 속력1마다 움직이는 것으로 코드를 구현하였다.

 

<전체 코드>

#include<iostream>
#include<vector>

using namespace std;

class shark
{
public:
	int speed, d, size;

	shark( int speed, int d, int size)
	{
		this->speed = speed;
		this->d = d;
		this->size = size;
	}
};

int n, m, k;
int dir[5][2] = { {-1,0},{1,0},{0,1},{0,-1} };
shark* shark_info[10002];  //상어id마다 정보 저장
int map[102][102];  //물속 지도
int tmp[102][102];   //임시 지도

int catch_shark(int column)    //해당 열 상어 잡기
{
	for (int i = 1; i <= n; i++)
	{
		if (map[i][column]!=0)   //상어가 있으면 잡기
		{
			int id = map[i][column];
			map[i][column]=0;
			return shark_info[id]->size;  //상어 사이즈 반환
		}
	}
	return 0;
}

int change_dir(int d)    //방향 반대로 바꾸기
{
	if (d == 1)return 2;
	else if (d == 2)return 1;
	else if (d == 3)return 4;
	
	return 3;
}

void copy_tmp_to_map()    //임시지도를 현실지도에 복사
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m ; j++)
		{
			map[i][j] = tmp[i][j];
		}
	}
}

void shark_move()    //상어 움직이기
{
	fill(&tmp[0][0], &tmp[100][101], 0);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int id = map[i][j];
			if (id == 0)continue;    //상어 없으면 스킵
			int speed = shark_info[id]->speed;
			int d = shark_info[id]->d;
			int size = shark_info[id]->size;
			
			int x = i;
			int y = j;
			for (int t = 0; t < speed; t++)  //speed만큼 상어 움직이기
			{
				int nextx = x + dir[d-1][0];
				int nexty = y + dir[d-1][1];
				if (nextx<1 || nexty<1 || nextx>n || nexty>m)//벽을 만난다면
				{
					d=change_dir(d);  //방향 반대로 바꾸기
					nextx = x + dir[d - 1][0];     //
					nexty = y + dir[d - 1][1];     //전진
				}
				x = nextx;
				y = nexty;
			}
	
			shark_info[id]->d = d;
			// 해당자리에 상어가 없거나,, 있는 상어보다 사이즈가 크면 자리 차지
			if ( tmp[x][y]==0 || shark_info[tmp[x][y]]->size < size)tmp[x][y] = id;		  	
		}
	}
	copy_tmp_to_map(); //tmp전부 map으로 복사
}

int main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> k;

	for (int i = 1; i <= k; i++)
	{
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;

		//움직이는 거리 최소화하기(안움직인거나 한바퀴 돌아서 제자리인거랑 같음)
		if (d == 1 || d == 2)s %= ((n * 2) - 2);  
		else s %= ((m * 2) - 2);                  

		shark_info[i] = new shark(s,d,z); //상어 정보 저장

		map[r][c] = i;  //map위치에 상어 id 저장
	}

	int sum = 0;
	for (int i = 1; i <= m; i++)
	{
		sum+=catch_shark(i);//i열의 상어 잡기

		shark_move();
	}
	printf("%d ", sum);


	return 0;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.