[백준/BOJ] 백준 2983번 : 개구리 공주

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

2983번: 개구리 공주

A, D 방향으로 가려면 x좌표-y좌표 값이 같은 점으로만 갈 수 있다는 점과, B, C방향으로 가려면 x좌표+y좌표 값이 같은 점으로만 갈 수 있다는 점을 이용하여, set<pair<int, int>> dir1에는 (x좌표-y좌표,x좌표(위치에서 가까운 점 찾기 위해))를 저장하고, set<pair<int, int>> dir2 에는 (x좌표+y좌표, x좌표(위치에서 가까운 점 찾기 위해))를 저장하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
using namespace std;

int n, k;
string moving;
set<pair<int, int>> dir1; //A,D방향 확인 (x좌표-y좌표,x좌표(위치에서 가까운 점 찾기 위해))(A,D방향으로 가려면 x좌표-y좌표 값이 같은 점으로만 갈 수 있다)
set<pair<int, int>> dir2; //B,C방향 확인 (x좌표+y좌표,x좌표(위치에서 가까운 점 찾기 위해))(B,C방향으로 가려면 x좌표+y좌표 값이 같은 점으로만 갈 수 있다)
set<pair<int, int>>::iterator it;
set<pair<int, int>>::iterator it2;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	cin >> moving;

	pair<int, int> here;
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;

		if (i == 0)
		{
			here = make_pair(x, y);
		}

		dir1.insert(make_pair(x - y, x));
		dir2.insert(make_pair(x + y, x));
	}

	for (int i = 0; i < moving.size(); i++)
	{
		pair<int, int> there;

		if (moving[i] == 'B')
		{
			//현재 위치
			it = dir2.find(make_pair(here.first + here.second, here.first));

			it++;

			//B방향에 갈 수 있는 곳이 있을때
			if (it != dir2.end() && (here.first + here.second == (*it).first))
			{
				there = make_pair((*it).second, (*it).first - (*it).second);

				//here위치의 정보는 dir1, dir2에서 삭제한다
				dir1.erase(make_pair(here.first - here.second, here.first));
				dir2.erase(make_pair(here.first + here.second, here.first));

				here = there;
			}

		}

		else if (moving[i] == 'D')
		{
			//현재 위치
			it = dir1.find(make_pair(here.first - here.second, here.first));

			if (it != dir1.begin())
			{
				it--;

				//D방향에 갈 수 있는 곳이 있을때
				if (here.first - here.second == (*it).first)
				{
					there = make_pair((*it).second, -((*it).first - (*it).second));

					//here위치의 정보는 dir1, dir2에서 삭제한다
					dir1.erase(make_pair(here.first - here.second, here.first));
					dir2.erase(make_pair(here.first + here.second, here.first));

					here = there;
				}
			}
		}


		else if (moving[i] == 'A')
		{
			//현재 위치
			it = dir1.find(make_pair(here.first - here.second, here.first));

			it++;

			//A방향에 갈 수 있는 곳이 있을때
			if (it != dir1.end() && (here.first - here.second == (*it).first))
			{
				there = make_pair((*it).second, -((*it).first - (*it).second));

				//here위치의 정보는 dir1, dir2에서 삭제한다
				dir1.erase(make_pair(here.first - here.second, here.first));
				dir2.erase(make_pair(here.first + here.second, here.first));

				here = there;
			}
		}

		else if (moving[i] == 'C')
		{
			//현재 위치
			it = dir2.find(make_pair(here.first + here.second, here.first));

			if (it != dir2.begin())
			{
				it--;

				//C방향에 갈 수 있는 곳이 있을때
				if (here.first + here.second == (*it).first)
				{
					there = make_pair((*it).second, (*it).first - (*it).second);

					//here위치의 정보는 dir1, dir2에서 삭제한다
					dir1.erase(make_pair(here.first - here.second, here.first));
					dir2.erase(make_pair(here.first + here.second, here.first));

					here = there;
				}
			}
		}
	}

	cout << here.first << " " << here.second << "\n";

	return 0;
}