백준 2983 개구리 공주 c++ (set)

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

2983번: 개구리 공주

문제

트럭을 타고 이동하던 중에 상근이는 휴식을 취하기 위해서 호수에 잠시 들렸다. 호수에는 개구리가 살고 있고, 개구리는 호수 위에 떠있는 식물 N개를 점프하면서 다닌다. 오래된 전설에 따르면 개구리에게 키스를 하면 개구리는 아름다운 공주로 변한다고 한다. 일단 개구리를 잡아야 전설이 사실인지 아닌지 확인할 수 있다. 개구리를 잡아보자.

호수는 2차원 평면으로 생각할 수 있고, 식물은 그 평면 위의 점으로 나타낼 수 있다. (x, y)위에 있는 개구리는 아래 네 가지 방향 중 한 방향으로 점프할 수 있다.

1. 임의의 양의 정수 P에 대해서, (x+P, y+P)로 점프할 수 있다. 이 방향을 A라고 한다.
2. 임의의 양의 정수 P에 대해서, (x+P, y-P)로 점프할 수 있다. 이 방향을 B라고 한다.
3. 임의의 양의 정수 P에 대해서, (x-P, y+P)로 점프할 수 있다. 이 방향을 C라고 한다.
4. 임의의 양의 정수 P에 대해서, (x-P, y-P)로 점프할 수 있다. 이 방향을 D라고 한다.

개구리는 네 방향 중 한 방향을 고른다. 그 다음 그 방향에 있는 가장 가까운 식물로 점프를 한다. 만약, 고른 방향에 식물이 없다면, 개구리는 그 위치에 그대로 있는다. 개구리가 점프를 하고 난 이후에, 원래 있던 식물은 호수로 가라앉게되고 사라진다.

상근이는 식물의 위치와 개구리가 고른 방향을 모두 알고 있다. 상근이는 개구리의 점프가 끝나는 꽃의 좌표를 알아낸 다음, 거기서 개구리를 잡으려고 한다.

개구리의 점프가 끝나는 식물의 위치는 어디일까?

입력

첫째 줄에 식물의 수 N과 점프의 수 K가 주어진다. (1 ≤ N, K ≤ 100,000)

둘째 줄에는 개구리가 고른 방향 K개가 주어진다. 이 방향은 'A','B','C','D'로만 이루어져 있다.

셋째 줄부터 N개 줄에는 식물의 좌표가 X, Y가 주어진다. (0 ≤ X, Y ≤ 1,000,000,000) 처음으로 주어지는 식물에 개구리가 있다.

출력

개구리의 점프가 끝나는 식물의 좌표를 출력한다.

알고리즘 분류

• 자료 구조
• 정렬
• 트리를 사용한 집합과 맵
• 연결 리스트

풀이

우선 문제 문맥상 동일한 좌표에 식물이 여러 개 있을 순 없는 것 같다.

아마 호수에 있는 연꽃잎을 생각하면.. 같은 자리에 여러 개가 있을 수 없다!

이런 느낌으로 배제하면 될 거 같다.

//실제로 동일한 좌표에 식물은 하나만 있다고 가정하고 풀어서 통과했다.

 

현 위치의 좌표를 x1,y1라고 하고, 다음 좌표를 x2,y2라고 하자.

개구리는 ABCD방향중, A,D방향으로 갈 땐 x1-y1 == x2-y2 값이 같아야 하고,

BC방향으로 갈 땐 x1+y1 == x2+y2 값이 같아야 점프할 수 있다.

또한 x를 기준으로(y를 기준으로 해도 된다.)

A방향일 때 x1 < x2

B방향일 때 x1 < x2 

C방향일 때 x1 > x2

D방향일 때 x1 > x2

를 만족해야 한다.

 

예를 들어 시작점이 5,6일 때, 방향이 B라면 7,4로 갈 수 있다.

5 + 6 == 7 + 4

5 < 7

두 개의 조건을 만족한다.

 

이제 규칙을 알았으니 구현을 해보자.

본인은 set과 tuple을 이용했는데, x+y혹은 x-y , x ,y  세 개의 값을 저장해야 하기 때문에 tuple을 이용했고,

문제에서 해당 방향에 있는 가장 가까운 식물로 점프를 한다고 했으니, set의 정렬 방식을 이용했다.

//tuple.first, tuple.second, tuple.third 순으로 오름차순

//x-y혹은 x+y값이 같으면 x값이 작은 순으로 저장된다.

 

이후 AD방향의 set 혹은 BC방향의 set에서 현재 좌표의 반복자를 찾은 후, x-y 혹은 x+y값이 같은 원소 중

이전 원소 혹은 다음 원소로 이동하고, 현재 좌표는 erase한다.

코드

#include <iostream>
#include <string>
#include <set>
#include <tuple>
using namespace std;

typedef tuple<int, int, int> tp;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	//ad는 x-y bc는 x+y
	set<tp> ad, bc;
	int N, K;
	string dir;
	int xpos, ypos;
	cin >> N >> K;	
	cin >> dir;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		ad.insert({ x - y,x,y });
		bc.insert({ x + y,x,y });
		if (i == 0) {
			xpos = x;
			ypos = y;
		}
	}
	
	for (int i = 0; i < dir.length(); i++) {
		int	curx = xpos;
		int	cury = ypos;
		if (dir[i] == 'A') {
			//현재 위치의 튜플 it
			set<tp>::iterator it = ad.find({ curx - cury, curx, cury });
			if (it == prev(ad.end()))//현재 it의 next를 검사하기 위한 예외처리
				continue;
			int minus,nextx, nexty;
			tie(minus, nextx, nexty) = *next(it);
			//A방향은x-y가 같을 때 x가 현재 it보다 큰 게 없으면 갈 곳 없음
			if (minus != curx - cury) {
				continue;
			}
			//현재 좌표 삭제
			ad.erase(it);
			bc.erase({ curx+cury,curx,cury });
			xpos = nextx;
			ypos = nexty;
		}
		else if (dir[i] == 'B') {
			//현재 위치의 튜플 it
			set<tp>::iterator it = bc.find({ curx + cury, curx, cury });
			if (it == bc.end())//현재 it의 next를 검사하기 위한 예외처리
				continue;
			int plus, nextx, nexty;
			tie(plus, nextx, nexty) = *next(it);
			//B방향은x+y가 같을 때 x가 현재 it보다 큰 게 없으면 갈 곳 없음
			if (plus != curx + cury) {
				continue;
			}
			//현재 좌표 삭제
			ad.erase({ curx-cury,curx,cury });
			bc.erase(it);
			xpos = nextx;
			ypos = nexty;
		}
		else if (dir[i] == 'C') {
			set<tp>::iterator it = bc.find({ curx + cury, curx, cury });
			if (it == bc.begin())//현재 it의 prev를 검사하기 위한 예외처리
				continue;
			int plus, nextx, nexty;
			tie(plus, nextx, nexty) = *prev(it);
			//C방향은x+y가 같을 때 x가 현재 it보다 작은 게 없으면 갈 곳 없음
			if (plus != curx + cury) {
				continue;
			}
			//현재 좌표 삭제
			ad.erase({ curx-cury,curx,cury });
			bc.erase(it);
			xpos = nextx;
			ypos = nexty;
		}
		else if (dir[i] == 'D'){
			//현재 위치의 튜플 it
			set<tp>::iterator it = ad.find({ curx - cury, curx, cury });
			if (it == ad.begin())//현재 it의 prev를 검사하기 위한 예외처리
				continue;
			int minus, nextx, nexty;
			tie(minus, nextx, nexty) = *prev(it);
			//D방향은x-y가 같을 때 x가 현재 it보다 작은 게 없으면 갈 곳 없음
			if (minus != curx - cury) {
				continue;
			}
			//현재 좌표 삭제
			ad.erase(it);
			bc.erase({ curx+cury,curx,cury });
			xpos = nextx;
			ypos = nexty;
		}
	}
	cout << xpos << ' ' << ypos;

	return 0;
}