백준 17143 낚시왕

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

17143번: 낚시왕

 

 

 

- 단순 빡구현 문제이다. 

 

- 내가 구현한 알고리즘의 경우, 시간복잡도는 O(r^2c^2)이다.

 

- shark가 위치한 좌표는 pair<pair<int,int>, pair<int, bool>> 자료형의 벡터로 관리했다. 왼쪽부터 각각 속력, 방향, 크기, 상어의 이동 여부를 의미한다. t가 c를 넘지 않을 동안 주어진 while문을 실행한다.

 

- 땅과 가장 가까운 상어를 잡고, 이후 상어의 이동을 시작한다. 일단 상어가 이동할 거리를 단축시켜주어 시간을 줄이는데, 상어의 방향과 평행인 두 방향(상어의 방향이 북쪽인경우, 북쪽과 남쪽)을 고려해서 줄여준다. 예를들어 2,3에 위치한 상어의 방향이 북쪽이고, R의 크기가 5라면 상어는 (R-1) * 2번의 이동 후에 현재 위치 및 방향과 동일하게 있게 된다. 따라서, 상어의 속력을 (R-1)*2 로 나눈 나머지를 구해서 그것에 대한 이동만 구해주면 된다.

 

- 다음으로, 상어의 이동시, 벽을 만났을 때이다. 상어가 만약 다음칸으로 이동하려는데, 해당 칸이 범위 밖이면 방향을 반대로 바꿔준다. 그 이후 한 칸을 전진하면 된다.

 

- 다음으로 조심해야 할 것은 상어의 이동 여부이다. 만약 어떤 상어가 이동을 완료하였는데, 이중 for문을 돌다보니 이동을 마친 상어가 또 선택될 수 있다. 따라서, 해당 상어의 bool형을 보고, 만약 true이면 이동을 마친 것이므로 continue를 해 주면 된다. 

 

- 이 모든 과정을 마쳤다면, 특정 칸에 여러 마리의 상어가 존재할 수 있다. 이 경우는 해당 칸을 sort를 해 주어서, 가장 큰 크기의 상어를 제외한 모든 상어들을 pop_back 해 주면 된다.

 

- 여태까지 푼 삼성 기출문제중에 손에 꼽는 문제였다.. 엄청나게 어려웠다기보다는 세세한 구현사항이 많았어서 디버깅을 엄청 오래했다. 총 소요시간은 1시간 30분정도.. 삼성이 3시간내에 2문제를 풀어야하니 조금 더 속도를 높일 필요가 있는 것 같다.ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <pair<pair<int, int>, pair<int, bool>>> shark[101][101];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };

bool compare(pair<pair<int, int>, pair<int, bool>> a, pair<pair<int, int>, pair<int, bool>> b) {
	return a.second.first > b.second.first;
}

int main() {
	int answer = 0;
	int R, C, M;
	cin >> R >> C >> M;
	for (int i = 0; i < M; i++) {
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;
		shark[r][c].push_back({ {s,d},{z,false} });
	}
	int t = 1;
	while (t <= C) {
		// 가장 가까운 상어 잡기
		for (int i = 1; i <= R; i++) {
			if (shark[i][t].size() != 0) {
				answer += shark[i][t][0].second.first;
				shark[i][t].pop_back();
				break;
			}
		}
		//상어 이동
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				if (shark[i][j].size() != 0) {
					if (shark[i][j][0].second.second) continue;
					int temp_s = shark[i][j][0].first.first;
					int shark_d = shark[i][j][0].first.second;
					int shark_z = shark[i][j][0].second.first;
					// 이동 횟수를 최대한 줄여준다.
					int real_s = temp_s % ((C - 1) * 2);
					if (shark_d == 1 || shark_d == 2) {
						real_s = temp_s % ((R - 1) * 2);
					}
					shark[i][j].erase(shark[i][j].begin());
					int real_i = i; int real_j = j;
					// 상어 이동
					while (real_s--) {
						if ((shark_d == 1 && real_i == 1) || (shark_d == 2 && real_i == R) || (shark_d == 3 && real_j == C) || (shark_d == 4 && real_j == 1)) {
							if (real_i + dx[shark_d - 1] < 1 || real_i + dx[shark_d - 1] > R || real_j + dy[shark_d - 1] < 1|| real_j + dy[shark_d - 1] > C) {
								if (shark_d % 2) shark_d += 1;
								else shark_d -= 1;
							}
						}
						real_i += dx[shark_d - 1];
						real_j += dy[shark_d - 1];
					}
					shark[real_i][real_j].push_back({ { temp_s,shark_d }, {shark_z, true} });
				}
			}
		}
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				if (shark[i][j].size() > 1) {
					sort(shark[i][j].begin(), shark[i][j].end(), compare);
					while (shark[i][j].size() > 1) shark[i][j].pop_back();
				}
				if(shark[i][j].size() == 1) shark[i][j][0].second.second = false;
			}
		}
	
		t++;
	}

	cout << answer;
	return 0;
}