[BOJ 17143] 낚시왕

문제출처

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

17143번: 낚시왕

 

문제풀이

 

처음에 시간복잡도를 생각 안하고 구현했더니 시간초과가 났다. 다음부터는 문제풀이 이전에 꼭 시간복잡도를 먼저 계산하고 풀이해야겠다.

 

이 문제는 상어의 정보가 주어지고 낚시왕이 왼쪽에서 오른쪽으로 이동하면서 잡은 상어의 크기의 총 합을 출력하는 문제이다.

문제에서 요구하는 구현사항은 2가지인데 순서에 맞게 구현해줘야 한다.

 

나 같은 경우는 낚시왕이 (0, 0)에서 시작해 x축 이동을 하면서 1번을 구현했다.

 

2번 조건을 구현하기 위해 catchShark(int x) 함수를 만들었다.

catchShark(int x) 함수

낚시왕이 위치한 x좌표를 넘겨줘서 y축 탐색을 해 가장 가까운 상어를 잡는 함수이다.

int catchShark(int x) {
	int ret = 0;
	for (int y = 1; y <= r; y++) {
		if (map[y][x] != 0) {
			ret = v[map[y][x]].z;
			v[map[y][x]].dead = 1;
			map[y][x] = 0;

			break;
		}
	}
	return ret;
}

 

3번 조건이 가장 까다로웠다. 이 조건은 moveShark() 함수를 만들었다.

moveShark() 함수

살아있는 상어 수만큼 반복하면서 상어 좌표를 이동해주는 함수이다. 행 처리와 열 처리가 같기 때문에 열 처리를 기준으로 설명하겠습니다.

여기서 가장 중요한게 speed = speed % ((c - 1) * 2) 부분인데 이 처리를 하지 않으면 시간초과가 납니다.

만약 r=4, c=6인 경우 상어가 방향전환을 하고 움직일때 1번 열과 6번 열은 1번씩만 자리잡고 2, 3, 4, 5번 열은 2번씩 자리잡는다. 

 

빨간 색을 1번만 위치하는 열이고 파랑색은 기존 위치 초록색을 방향전환을 했을때 자리잡는 위치이다. 이 표를 가지고 시뮬레이션을 해보면 규칙을 파악할 수 있다. 이 규칙을 이용해서 반복횟수를 줄여 시간초과를 벗어나면 된다.

 

이후 조건에 따라 구현해줬다. 상어가 이동한 자리가 빈칸이면 상어 번호를 map에 저장하고 움직인 상어가 위치한다면 크기를 비교해 먹거나 먹히도록 구현했다. 움직이지 않은 상어가 위치하는 경우는 반복문을 통해 나중에 처리하기 때문에 현재 위치한 상어를 위치시키면 된다.

 

void moveShark() {
	for (int i = 1; i <= m; i++) {

		// 죽은 상어는 건너뛴다
		if (v[i].dead) continue;

		// 움직일 상어 정보
		int y = v[i].r;
		int x = v[i].c;
		int speed = v[i].s;
		int dir = v[i].d;
		int size = v[i].z;

		// 현재 움직일 상어 기존 위치 초기화
		if (map[y][x] == i) map[y][x] = 0;

		// 위, 아래
		if (dir == 0 || dir == 1) {
			speed = speed % ((r - 1) * 2);
			
			while (speed--) {
				int ny = y + dy[dir];
				if (1 > ny || ny > r) dir = 1 - dir;
				y += dy[dir];
			}
		} 
		
		// 오른쪽 왼쪽
		else { 
			speed = speed % ((c - 1) * 2);

			while (speed--) {
				int nx = x + dx[dir];
				if (1 > nx || nx > c) dir = 5 - dir;
				x += dx[dir];
			}
		}

		// 이동한 상어 위치 최신화
		v[i].r = y;
		v[i].c = x;
		v[i].d = dir;

		// 이동한 위치가 빈칸인 경우 => 위치 이동
		if (map[y][x] == 0) {
			map[y][x] = i;
		} 

		// 이동한 위치에 이미 이동을 완료한 상어가 있는 경우 => 잡아먹거나 잡아 먹힘
		else if (i > map[y][x]) { 

			// 이동한 상어의 사이즈가 더 큰 경우
			if (size > v[map[y][x]].z) {
				v[map[y][x]].dead = 1;
				map[y][x] = i;
			}

			// 이동한 상어의 사이즈가 더 작은 경우 
			else {
				v[i].dead = 1;
			}
		} 
		
		// 이동한 위치에 아직 이동 안 한 상어가 있는 경우 => 이후에 재 처리하기 때문에 뒤집어 씌움
		else { 
			map[y][x] = i;
		}
	}
}

 

기존에 시간초과했던 방법 즉, 문제대로 그냥 구현한 방법의 시간복잡도는 다음과 같다.

상어의수(10000) X 속도(1000) X 낚시왕이 움직이는 열의 수(100) 

= 10^4 * 10^3 * 10^2 = 10^9 = 1,000,000,000 (10억) 번의 연산이 필요하다.

1초에 1억번 계산가능하다는 가정하에 이 문제는 단순 구현으로는 1초안에 해결할 수 없다.

 

시간 초과때문에 힘들었던 문제인데 진짜 시간복잡도를 먼저 계산하는게 왜 중요한지 다시 깨우친 문제이다. 시험장에서였으면 아마 시간초과로 탈락했을거 같다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_17143/boj17143.cpp

sw93/algorithm

 

#include <iostream>
#include <vector>
using namespace std;
struct SHARK {
	int r, c, s, d, z;
	bool dead;
};
int r, c, m;
int map[101][101];
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
vector<SHARK> v;

void init() {
	cin >> r >> c >> m;

	// 1번부터 시작
	v.push_back({ 0,0,0,0,0,0 });
	for (int i = 1; i <= m; i++) {
		SHARK shark;
		cin >> shark.r >> shark.c >> shark.s >> shark.d >> shark.z;
		shark.dead = 0;
		shark.d -= 1;
		v.push_back(shark);
		map[shark.r][shark.c] = i;
	}
}

int catchShark(int x) {
	int ret = 0;
	for (int y = 1; y <= r; y++) {
		if (map[y][x] != 0) {
			ret = v[map[y][x]].z;
			v[map[y][x]].dead = 1;
			map[y][x] = 0;

			break;
		}
	}
	return ret;
}

void moveShark() {
	for (int i = 1; i <= m; i++) {

		// 죽은 상어는 건너뛴다
		if (v[i].dead) continue;

		// 움직일 상어 정보
		int y = v[i].r;
		int x = v[i].c;
		int speed = v[i].s;
		int dir = v[i].d;
		int size = v[i].z;

		// 현재 움직일 상어 기존 위치 초기화
		if (map[y][x] == i) map[y][x] = 0;

		// 위, 아래
		if (dir == 0 || dir == 1) {
			speed = speed % ((r - 1) * 2);
			
			while (speed--) {
				int ny = y + dy[dir];
				if (1 > ny || ny > r) dir = 1 - dir;
				y += dy[dir];
			}
		} 
		
		// 오른쪽 왼쪽
		else { 
			speed = speed % ((c - 1) * 2);

			while (speed--) {
				int nx = x + dx[dir];
				if (1 > nx || nx > c) dir = 5 - dir;
				x += dx[dir];
			}
		}

		// 이동한 상어 위치 최신화
		v[i].r = y;
		v[i].c = x;
		v[i].d = dir;

		// 이동한 위치가 빈칸인 경우 => 위치 이동
		if (map[y][x] == 0) {
			map[y][x] = i;
		} 

		// 이동한 위치에 이미 이동을 완료한 상어가 있는 경우 => 잡아먹거나 잡아 먹힘
		else if (i > map[y][x]) { 

			// 이동한 상어의 사이즈가 더 큰 경우
			if (size > v[map[y][x]].z) {
				v[map[y][x]].dead = 1;
				map[y][x] = i;
			}

			// 이동한 상어의 사이즈가 더 작은 경우 
			else {
				v[i].dead = 1;
			}
		} 
		
		// 이동한 위치에 아직 이동 안 한 상어가 있는 경우 => 이후에 재 처리하기 때문에 뒤집어 씌움
		else { 
			map[y][x] = i;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();

	// 예외 처리
	if (m == 0) {
		cout << 0;
		return 0;
	}

	int ans = 0;
	for (int x = 1; x <= c; x++) {
		ans += catchShark(x);
		moveShark();
	}
	cout << ans;
	return 0;
}