[백준 17143] 낚시왕

 

문제

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

17143번: 낚시왕

 

문제 풀이

단순하게 시간복잡도를 생각해본다면 $O(C*M*s)$ = $O(10^9)$로 TLE가 남

따라서 상어의 움직임을 줄여야 했고 아래의 관찰을 통해 해결함

• (상어 H가 같은 위치로 돌아오는데 걸리는 시간) = (오른쪽으로 갔다가 돌아오는 시간) + (왼쪽으로 갔다가 돌아오는 시간)  

• 이는 좌표를 우측 90도 방향으로 돌렸을때, (위,아래)로 움직이는 상어들도 동일하게 적용됨

• 따라서 같은 위치로 돌아오는 주기  $ T = 2 *(R -1) , T = 2 *(C-1)$ (∵ 양 끝 점은 한 번씩만 방문)   

	if (di <= 2) v %= (2 * (R - 1)); // (dir <= 2) : left, right
	else v %= (2 * (C - 1)); // (dir >= 3) : up, down

 

코드

#include <bits/stdc++.h>
using namespace std;

const int dir[5][2] = { { 0,0 },{ -1,0 },{ 1,0 },{ 0,1 },{ 0,-1 } };
struct shark {
	int s, d, z;
};
int R, C, M, a, b, c, d, e, grid[101][101], tmp[101][101], ans;
shark f[10001];

void moveNeat() {
	memset(tmp, 0, sizeof(tmp));
	int v, sz, di, nr, nc;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (grid[i][j]) {
				v = f[grid[i][j]].s, di = f[grid[i][j]].d, sz = f[grid[i][j]].z;
				nr = i, nc = j;
				if (di <= 2) v %= (2 * (R - 1));
				else v %= (2 * (C - 1));
				while (v--) {
					if ((nr == 1 && di == 1) || (nr == R && di == 2)) di = 3 - di;
					else if ((nc == 1 && di == 4) || (nc == C && di == 3)) di = 7 - di;
					nr += dir[di][0], nc += dir[di][1];
				}
				f[grid[i][j]].d = di;
				if (!tmp[nr][nc]) tmp[nr][nc] = grid[i][j];
				else if (f[tmp[nr][nc]].z < f[grid[i][j]].z) tmp[nr][nc] = grid[i][j];
			}
		}
	}
	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			grid[i][j] = tmp[i][j];
}

void fishing(int pos) {
	for (int i = 1; i <= R; i++) {
		if (grid[i][pos]) {
			ans += f[grid[i][pos]].z;
			grid[i][pos] = 0;
			break;
		}
	}
}
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> R >> C >> M;
	for (int i = 1; i <= M; i++) {
		cin >> a >> b >> c >> d >> e;
		f[i] = { c,d,e };
		grid[a][b] = i;
	}

	for (int t = 1; t <= C; t++) {
		fishing(t);
		moveNeat();
	}
	cout << ans;
}

 

어떻게 구현 ?

 

위의 생각까지 마쳤다면 두 함수를 구현할 수 있음

 

1. 상어를 잡는 함수

void fishing(int pos) {
	for (int i = 1; i <= R; i++) {
		if (grid[i][pos]) {
			ans += f[grid[i][pos]].z;
			grid[i][pos] = 0;
			break;
		}
	}
}

 

2. 상어의 움직임을 제어하는 함수

 

memset(tmp, 0, sizeof(tmp));

 ⑴ 이동할 좌표에 상어정보 초기화

 

if ((nr == 1 && di == 1) || (nr == R && di == 2)) di = 3 - di;
else if ((nc == 1 && di == 4) || (nc == C && di == 3)) di = 7 - di;

 ⑵ 격자판의 끝 점에서 상어의 방향이 격자판 바깥을 향한다면 반대방향으로 돌려줌 

 

f[grid[i][j]].d = di; 

 ⑶ 이동이 끝난 후 해당 상어의 방향을 교체해줌

 

/* tmp[nr][nc] : 이동할 좌표의 상어인덱스
   f[grid[i][j]] : 이동전 좌표의 상어인덱스*/

if (!tmp[nr][nc]) tmp[nr][nc] = grid[i][j]; 
else if (f[tmp[nr][nc]].z < f[grid[i][j]].z) tmp[nr][nc] = grid[i][j];

 ⑷ 이동한 좌표에 상어가 없다면 상어의 인덱스를 저장하고, 상어가 존재한다면 크기를 비교하여 크기가 더 큰 상어의 인덱스를 저장

 

 

for (int i = 1; i <= R; i++)
	for (int j = 1; j <= C; j++)
		grid[i][j] = tmp[i][j];

 ⑸ 이동한 좌표의 상어정보를 현 좌표에 갱신