[백준 17143] 낚시왕

인간은 같은 실수를 반복하고...

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

17143번: 낚시왕

#include <cstdio>
int R, C, M;
int Shark[100 + 2][100 + 2];

struct _st
{
	int x, y;	// 상어위치
	int s;		// 속력
	int d;		// 방향
	int z;		// 크기
	bool alive;	// 생존여부
};
_st Info[10000 + 2];


void input()
{
	scanf("%d %d %d", &R, &C, &M);	// 행, 열, 상어 수
	for (int i = 1; i <= M; i++) {
		int r = 0, c = 0, s = 0, d = 0, z = 0;
		scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
		Info[i] = { r, c, s, d, z, true};
		Shark[r][c] = i;	// (r, c)위치에 i번째 상어 존재 
	}
}


int catch_shark(int col)
{
	for (int i = 1; i <= R; i++) {
		if (Shark[i][col] != 0 && Info[Shark[i][col]].alive == true) {
			int get = Info[Shark[i][col]].z;
			Info[Shark[i][col]] = {-1, -1, -1, -1, -1, false};
			Shark[i][col] = 0;
			return get;
		}
	}
	return 0;
}


void  move_shark()
{
	// 0 1상 2하 3우 4좌
	static int dir_x[5] = { 0, -1, 1, 0, 0 };
	static int dir_y[5] = { 0, 0, 0, 1, -1 };
	static int dir_op[5] = { 0, 2, 1, 4, 3 };
	
	for (int i = 1; i <= M; i++) {
		if (Info[i].alive == false) continue;
		int x = Info[i].x;
		int y = Info[i].y;
		//int speed = Info[i].s;
		int dir = Info[i].d;

		int speed = Info[i].s;
		if (dir == 1 || dir == 2) speed %= (R - 1) * 2;
		else speed %= (C - 1) * 2;

		for (int i = 0; i < speed; i++) {
			int nx = x + dir_x[dir];
			int ny = y + dir_y[dir];
			if (nx < 1 || nx > R || ny < 1 || ny > C) {
				dir = dir_op[dir];
				nx = x + dir_x[dir];
				ny = y + dir_y[dir];
			}
			x = nx, y = ny;
		}
		Info[i].x = x;
		Info[i].y = y;
		Info[i].d = dir;
	}
}


void kill_shark()
{
	
	std::fill(&Shark[0][0], &Shark[0][0] + sizeof(Shark) / sizeof(int), 0);

	for (int i = 1; i <= M; i++) {
		if (Info[i].alive == false) continue;
		int x = Info[i].x;
		int y = Info[i].y;
		int speed = Info[i].s;
		int dir = Info[i].d;
		int size = Info[i].z;

		if (Shark[x][y] == 0) Shark[x][y] = i;
		else {
			if (Info[Shark[x][y]].z < size) {
				Info[Shark[x][y]] = { -1, -1, -1, -1, -1, false };
				Shark[x][y] = i;
			}
			else if (Info[Shark[x][y]].z > size) Info[i] = { -1, -1, -1, -1, -1, false };
		}
	}
}



int simul()
{
	int total = 0;
	for (int t = 1; t <= C; t++) {
		//debug();
		total += catch_shark(t);
		move_shark();
		kill_shark();
		//printf("move & kill\n");
		//debug();
	}
	return total;
}



int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}

 

사실 틀릴거 알고 제출했다. 

지난번에 풀 때 이해를 못한 부분을 드디어 이해하고 제출 후 AC...

상어를 하나하나 옮기면 speed가 1000까지 있기 때문에 최대 10,000마리의 상어가 100 * 100 맵에서 모두 속력 1000으로 이동하면 연산의 크기가 굉장히 많아진다. 이 때문에 모듈러스 연산이 필요한데, 이 문제의 경우 행과 열의 크기가 다르기 때문에 따로 각각의 경우를 따로 구해야 한다. 

 

1. 움직이는 방향이 상 / 하 인 경우

상어가 움직이다가 영역 밖을 2번 만나고, 열의 모든 칸을 거쳐서 다시 자기 자리로 되돌아 오려면 (R - 1) * 2 번 움직여야 한다. 5 * 5맵에서 (2, 3)에 상어가 있고, 상 방향으로 이동하는 경우 자기 자리로 되돌아 오는 경로는 다음과 같다.

: (1, 3) -> (2, 3) -> (3, 3) -> (4, 3) -> (5, 3) -> (4, 3) -> (3, 3) -> (2, 3) 

2. 움직이는 방향이 좌 / 우 인 경우

위와 비슷하게 상어가 움직이다가 영역 밖을 2번 만나고, 행의 모든 칸을 거쳐서 다시 자기 자리로 되돌아 오려면 (C - 1) * 2번 움직여야 한다. 5 * 5 맵에서 (2, 3)에 상어가 있고, 좌 방향으로 이동하는 경우 자기 자리로 되돌아 오는 경로는 다음과 같다. 

: (2, 2) -> (2, 1) -> (2, 2) -> (2, 3) -> (2, 4) -> (2, 5) -> (2, 4) -> (2, 3)

---

이전 코드는 다음과 같다. 

압도적인 실행시간... 창피하다 ... ^^;

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
int R, C, M;

struct _vt	// 벡터용
{
	int speed;
	int dir;
	int size;
};

struct _qt
{
	int x;
	int y;
	int s;		// 속력
	int d;		// 방향
	int sz;		// 사이즈 
};



bool COMP(_vt &a, _vt &b)
{
	return a.size > b.size;		// 각 칸 별로 사이즈 기준으로 상어 정렬할 때 이용 
}


std::vector<_vt> Ocean[100 + 2][100 + 2];
std::queue<_qt> Q;



void input()
{
	scanf("%d %d %d", &R, &C, &M);	// 격자판 행, 열, 상어 수 
	for (int i = 0; i < M; i++) {
		int r = 0, c = 0, s = 0, d = 0, z = 0;
		scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
		Ocean[r][c].push_back({ s, d % 4, z });		// 방향벡터 0~3
	}
}



void eat_shark()
{
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			int o_sz = Ocean[i][j].size();
			if (o_sz > 1) {	// 해당 칸에 상어가 한 마리 보다 많이 있는 경우 서로 잡아먹어야 한다. 
				std::sort(Ocean[i][j].begin(), Ocean[i][j].end(), COMP);	// 사이즈를 기준으로 해당 칸에 있는 상어들을 정렬한다. 
				_vt tmp = Ocean[i][j][0];
				Ocean[i][j].clear();
				Ocean[i][j].push_back({ tmp });
			}
		}
	}
}



void mv_shark()
{
	// 
	static int dir_x[4] = { 0, -1, 1, 0 };
	static int dir_y[4] = { -1, 0, 0, 1 };
	static int dir_op[4] = { 3, 2, 1, 0 };

	// 맵에 남아있는 상어 정보 큐에 담기 
	Q = {};
	for (int j = 1; j <= C; j++) {
		for (int i = 1; i <= R; i++) {
			if (Ocean[i][j].size() > 0) {
				Q.push({ i, j, Ocean[i][j][0].speed, Ocean[i][j][0].dir, Ocean[i][j][0].size });
				Ocean[i][j].clear();		// 상어 이동할 것이므로 
			}
		}
	}

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		// 상어이동
		int nx = data.x; int ny = data.y; int nd = data.d;	int speed = data.s;
		if (nd == 1 || nd == 2) speed %= 2 * (R - 1);
		else speed %= 2 * (C - 1);
		for (int s = 1; s <= speed; s++) {
			nx += dir_x[nd];
			ny += dir_y[nd];
			if (nx < 1 || nx > R || ny < 1 || ny > C) {
				nd = dir_op[nd];	// 속도는 유지, 방향은 반대로
				nx += (2 * dir_x[nd]);
				ny += (2 * dir_y[nd]);
			}
		}
		Ocean[nx][ny].push_back({ data.s, nd, data.sz });
	}
	eat_shark();
}




int chk_shark(int col)
{
	int sum = 0;
	for (int i = 1; i <= R; i++) {			// 2. 낚시왕이 있는 열에 있는 상어 중 땅과 가장 가까운 상어를 잡음.
		if (!Ocean[i][col].empty()) {
			sum += Ocean[i][col][0].size;	// 이미 상어들끼리 잡아먹은 후 이므로 해당 칸에는 무조건 상어 한마리만 남을 것임
			Ocean[i][col].clear();			// 해당 칸의 상어정보 없애줌	// 이동 방지
			break;
		}
	}
	return sum;
}


int simul()
{
	int total = 0;
	for (int j = 1; j <= C; j++) {
		int cnt = chk_shark(j);	// 해당 열에 상어가 있는지 확인하고 잡기 
		total += cnt;
		mv_shark();				// 상어 이동 
	}
	return total;
}



int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}

 

진짜 리터럴리 아침에 눈뜨자마자 푼 문제 ^^;;;;;

 

 

맵의 각 칸에 상어의 정보를 저장하기 위해 2차원 벡터 Ocean을 선언했다. 

그리고 상어가 이동을 마친 후, 한 칸에 상어가 두 마리 있는 경우에는 크기가 가장 큰 상어만 남게하기 위해 COMP 비교함수를 만들어 놓았다. 이것으로 각 칸에 살고있는 상어를 사이즈 기준으로 내림차순 정렬할 것이다. 

 

 

// input( ) 함수

이때 주의해야할 것은 문제에서 숫자와 방향을 특정지어 주었고, "1 - 상 2 - 하 3 - 우 4 - 좌" 순이다.

처음에 이를 간과하고 문제 풀다가 디버깅 지옥에 갇혀버릴뻔... 그리고 방향벡터를 만들 때 인덱스를 0부터 선언해주었기 때문에, 이에 맞추어서 입력받을 때부터 d % 4 로 변환했다. 결국 "0 - 좌 1 - 상 2 - 하 3 - 우" 순이 된다. 

 

 

// simul( ) 함수

문제에서 준 순서대로 함수를 구현하였다. 

1. 낚시왕은 열의 시작부터 끝 인덱스 까지만 돌기 때문에 for 루프를 해당 범위에서만 돌려준다.

2. chk_shark 함수를 통해 해당 열에 상어가 있으면 잡고, 이에 대한 리턴값을 total 변수에 저장한다. 

3. mv_shark 함수를 통해 상어를 이동시킨다. 

 

 

// mv_shark( ) 함수

낚시왕이 잡은 상어를 제외하고, 여전히 맵에 남아있는 상어들의 정보를 큐에 담아주었다. 

그리고 큐가 빌 때까지 루프를 돌면서 상어들을 이동시켜준다. 

이때 중요한 점은 상어를 0부터 speed(상어의 속도)전 까지 한 칸씩 움직이면 타임아웃 난다는 것이다. 왜냐하면 상어의 속도가 1000까지 될 수 있기 때문이다. 최대 10000마리의 상어가 각각 1000초의 속도로 움직이는데 맵의 열 크기가 100이라면 이때의 연산은 10^9번 이루어질 것이다. 나의 시간초과 2번은 모두 이 부분이었다. 

그래서 모듈러스 연산을 수행하였다. 

더 자세한 설명은 아래 블로그를 참고하기를 바란다... ! 

https://yabmoons.tistory.com/288