[백준 2983] 개구리 공주

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

2983번: 개구리 공주

 

요구사항

점프 방향과 꽃의 위치가 주어졌을 때 마지막으로 개구리가 위치하는 좌표 찾기

 

풀이

그래프로 그려서 보면 현재 좌표 (x,y)에서 방향 A, B, C, D로 갈 수 있는 곳은 x+y가 같은곳 혹은 x-y 값이 같은 곳이다

 

1. set 자료구조를 활용하여 자료를 저장할 수 있도록 한다.

2. 세개의 자료를 저장하기 위해서 tuple사용

3. 각 조건에 따라 구현

 

바킹독님 풀이 참조하였다 어려워...

https://blog.encrypted.gg/589

#include <map>

#include <set>

#include <tuple>

#include <iostream>

 

using namespace std;

typedef tuple<int, int, int> ti3;

typedef pair<int, pair<int, int> > p;

set<ti3> splus;
set<ti3> sminus;

 

char dir[100010];

 

int n, m;

int xpos;

int ypos;

int main() {

	scanf("%d%d", &n, &m);

	scanf("%s", dir);

	for (int i = 0; i < n; i++) {

		//cout << i << endl;

		int x, y;

		scanf("%d%d", &x, &y);

		if (i == 0) {
			xpos = x;
			ypos = y;
		}

		splus.insert({x+y,x,y} );

		sminus.insert( {x-y,x,y } );

	}

	//set<ti3>::iterator iter;

	for (int i = 0; dir[i] != 0; i++) {
		int nowx = xpos;
		int nowy = ypos;
		if (dir[i] == 'A') {
			auto iter = sminus.find({ nowx - nowy,nowx,nowy });
			if (iter == prev(sminus.end()) ) {
				continue;
			}
			int minus, nextx, nexty;
            tie(minus, nextx,nexty) = *next(iter);
			if (minus != nowx - nowy) {
				continue;
			}
			sminus.erase(iter);
			splus.erase({ nowx + nowy,nowx,nowy });
			xpos = nextx;
			ypos = nexty;
		}

		else if (dir[i] == 'B') {
		    auto iter = splus.find({ nowx + nowy,nowx,nowy });
			if (iter == prev(splus.end() )) {
				continue;
			}
            int plus, nextx, nexty;
            tie(plus, nextx,nexty) = *next(iter);
			if (plus != nowx + nowy) {
				continue;
			}
			sminus.erase({ nowx - nowy,nowx,nowy });
			splus.erase({ nowx + nowy,nowx,nowy });
			xpos = nextx;
			ypos = nexty;
		}

		else if (dir[i] == 'C') {
			auto iter = splus.find({ nowx + nowy,nowx,nowy});
			if (iter == splus.begin()) {
				continue;
			}
            int plus, nextx, nexty;
            tie(plus, nextx,nexty) = *prev(iter);
			if (plus != nowx + nowy) {
				continue;
			}
			sminus.erase({ nowx - nowy,nowx,nowy });
			splus.erase({ nowx + nowy,nowx,nowy });
			xpos = nextx;
			ypos = nexty;
		}
		else if (dir[i] == 'D') {
			auto iter = sminus.find({ nowx - nowy,nowx,nowy });
			if (iter == sminus.begin()) {
				continue;
			}
            int minus, nextx, nexty;
            tie(minus, nextx,nexty) = *prev(iter);
			if (minus != nowx - nowy) {
				continue;
			}
			sminus.erase({ nowx - nowy,nowx,nowy });
			splus.erase({ nowx + nowy,nowx,nowy });
			xpos = nextx;
			ypos = nexty;
		}
	}
	printf("%d %d", xpos, ypos);
    }