백준 17143 낚시왕 c++ (시뮬레이션)

문제 출처 : https://www.acmicpc.net/problem/17143

17143번: 낚시왕

문제

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

입력

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

출력

낚시왕이 잡은 상어 크기의 합을 출력한다.

초기 상태

1초

2초 (E번 상어는 B번에게 먹혔다)

3초

4초

5초

6초

알고리즘 분류

• 구현
• 시뮬레이션

풀이

삼성 기출 시뮬레이션 구현 문제이다.

문제의 풀이는 크게 아래 3가지 단계로 분류된다.

1. 낚시 (같은 열에 있는 상어 중, 행의 숫자가 가장 낮은 상어를 낚는다.)

2. 상어의 이동(상어는 속력만큼 좌우/상하로 이동한다.)

3. 상어끼리의 사냥(같은 칸에 도착한 상어는 크기가 큰 놈이 작은 놈들을 잡아먹는다.)

 

우선 상어의 정보는

좌표값 : r, c

속력 : s

방향 : d

크기 : z

를 포함해야 하기 때문에, 이를 저장할 구조체를 만들어 사용한다.

본인은 그래프에서 각 열마다 상어들을 행 기준 오름차순으로 정렬, 저장할 priority_queue[100]을 사용하였다.

 

1번 과정을 먼저 보면,

낚시왕은 0열부터 C-1열까지 이동한다. 

각각의 열을 방문하면서, pq의 top()에는 각각의 열의 가장 행이 낮은 상어가 저장되어 있기 때문에,

이 상어를 pop()(낚시)한다.

만약 해당 열에 pq가 비었다면, 해당 열에는 상어가 없다는 뜻으로 넘어간다.

 

2번 과정은, 1번 과정에서 상어를 낚았든, 낚지 않았든 매번 상어는 이동한다.

여기서, 상어의 이동을 s(속력)만큼 루프를 돌아서 이동한다면 속력은 최대 1000이고, 상어는 최대 10000마리이므로, 매번 속력만큼 루프를 돌아 상어의 이동을 구현한다면 시간 초과가 날 것이다.

루프를 줄이는 방법으로는,

상어가 오른쪽 혹은 왼쪽 방향을 가리키고 있을 때, 같은 방향을 가리키며 제자리로 돌아오기까지는 (C-1)*2번 만큼의 이동이 필요하다.

위쪽, 아래쪽 방향을 가리키고 있을 때는 마찬가지로, (R-1)*2번 만큼의 이동을 하면 같은 방향을 가리키며 제자리로 돌아온다.

예를 들어 상어의 속력이 25이고, 방향은 오른쪽, 그래프의 열은 6이라고 하자. (6-1)*2번마다 상어는 제자리, 같은 방향으로 돌아올 것이기 때문에, 25를 10으로 나눈 나머지인 5만큼만 이동하면 상어의 최종 위치를 알 수 있다.

즉, 상어의 속력 및 방향을 입력받을 때, s %= (C-1)*2 혹은 s %= (R-1)*2로 상어의 이동을 최소화할 수 있다.

 

3번 과정은, 2번 과정에서 상어의 이동이 이루어졌을 때, 같은 행/열에 상어가 여러 마리 있다면, 가장 z가 큰 상어만 남고 작은 상어들은 없어지는 것을 구현해야 한다. 본인은 map을 이용해, map의 key를 상어의 좌표 값으로 사용하여, 중복되는 좌표에 대해 상어의 크기를 비교해 가장 큰 놈만 남겼다.

처음엔 예제는 다 맞고 게시판의 반례들도 통과했지만, 코드를 제출하면 계속 채점 %도 올라가지 않고 바로 '틀렸습니다'가 떴는데, string자료형의 key를 저장하는 방식에서 r+c 방식으로 저장하여, 실제 좌표가 다른 경우,

r = 1 c = 11, c = 1 r= 11의 경우도 같은 좌표로 인식해서 틀렸던 것이었다.

이는 r+c 사이에 공백을 넣는 r+" "+c의 형태로 key를 만듦으로써 해결하였다.

 

본인은 2차원 그래프를 사용하지 않고, 열에 대한 1차원 그래프에 우선순위 큐를 넣어 사용했는데,

2차원 그래프를 사용하는 것이 훨씬 빠르게 동작할 것이다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;


//2<=r<=c<=100
//0<=m<=r*c
//0<=s<=1000
//1<=d<=4 상하우좌 ^1로방향역전
//1<=z<=10000

struct Shark {
	int r;
	int c;
	int s;
	int d;
	int z;
};

struct cmp {
	bool operator()(const Shark &a, const Shark &b) {
		return a.r > b.r;
	}
};

int R, C, M;
//열별로 저장된 상어의 행 오름차순
priority_queue<Shark, vector<Shark>, cmp> sharks[101];
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };

bool isInside(int curR,int curC){
	if (curR < 0 || curR >= R || curC < 0 || curC >= C) return false;
	return true;
}

void moveShark() {
	
	unordered_map<string,Shark> ma;
	for (int i = 0; i < C; i++) {
		while (!sharks[i].empty()) {
			//한 마리씩 이동
			Shark shark = sharks[i].top();
			for (int j = 0; j < shark.s; j++) {
				if (!isInside(shark.r+dir[shark.d][0], shark.c+dir[shark.d][1])) {
					shark.d = shark.d ^ 1;
				}
				shark.r += dir[shark.d][0];
				shark.c += dir[shark.d][1];
			}

			string key = to_string(shark.r)+" "+to_string(shark.c);
			//상어 좌표가 겹치면 사이즈 큰 상어로 갱신(잡아먹기)
			if (ma[key].z!=0){
				if (shark.z > ma[key].z) {
					ma[key] = shark;
				}
			}
			else {
				ma[key] = shark;
			}
			sharks[i].pop();
		}
	}
	
	//map에 저장된 이동된 상어들을 sharks에 옮기기
	for (auto o : ma) {
		sharks[o.second.c].push(o.second);
	}
}

int solve(){
	int result = 0;
	//낚시왕의 이동
	for (int i = 0; i < C; i++) {
		//해당 열에 상어가 있으면 점수 +
		if (sharks[i].empty()) {
			moveShark();
			continue;
		}
		int topR = sharks[i].top().r;
		result += sharks[i].top().z;
		sharks[i].pop();
        
		//살아남은 상어 이동
		moveShark();
	}

	return result;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> R >> C >> M;
	
	for (int i = 0; i < M; i++) {
	//s속력 d방향 z크기 
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;
		//열 별로 상어를 저장
        if (d >= 3) {
			s %= (C - 1) * 2;
		}
		//상하
		else {
			s %= (R - 1) * 2;
		}
		sharks[c-1].push({ r-1,c-1,s,d-1,z });
	}
	cout <<solve();
	return 0;
}