[백준 27971] 강아지는 많을수록 좋다 (C++)

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

문제

---

마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 N마리를 집에서 키우기로 결심했다!

호무라는 한 번의 행동에서 다음 2$2$가지 마법 중 하나를 선택하여 사용한다. 가장 처음에는 호무라의 집에 강아지가 존재하지 않는다.

•  A-생성 마법: 강아지 A$A$마리를 호무라의 집에 생성한다.
•  B-생성 마법: 강아지 B$B$마리를 호무라의 집에 생성한다.

그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다. 만약 호무라의 방에 생성된 강아지의 수가 M개의 닫힌구간들 [L1,R1],[L2,R2],⋯,[LM,RM] 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 강아지가 사라지게 된다!

이를 명심하면서, 호무라는 위의 2가지 마법을 적절히 사용하여, 최소의 행동 횟수로 호무라의 집에 정확히 N마리의 강아지가 있도록 만들고 싶다. 계산을 어려워하는 호무라를 위해 최소의 행동 횟수를 계산해주자!

 

입력

---

첫 번째 줄에 키우기를 원하는 강아지의 수 N(2 ≤ N ≤ 100000), 제약 사항에 해당하는 닫힌구간의 개수 M(1 ≤ M ≤ 100), 그리고 A와 B(1≤A, B≤N)가 띄어쓰기로 구분되어 주어진다. 그 다음 M줄에 걸쳐서, 각 줄에 제약 사항에 해당하는 닫힌구간의 양 끝점이 주어진다. 1 ≤ i ≤ M에 대하여 Li와 Ri는 1이상 N−1 이하의 정수이며, Li ≤ Ri이다.

 

출력

---

첫 번째 줄에 정확히 N마리의 강아지를 호무라의 집에 들일 수 있는 최소의 행동 횟수를 출력한다. 만약 불가능하다면 −1을 출력한다.

 

문제 풀이

---

너비 우선 탐색 문제.

 

0마리에서 시작하고, N마리까지 A나 B마리를 추가해 도달할 수 있는지 확인해주면 된다. 단, 닫힌 구간이 있으므로 현재 front에 A나 B를 더했을 때 그 값이 닫힌 구간 안에 속한다면 큐에 넣지 않으면 된다. 닫힌 구간의 수가 100으로 적으므로, 해당 수가 닫힌 구간 안에 있는지 확인할 때 단순 반복문을 사용해도 된다.

 

아래는 코드.

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
bool* isVisited;

vector<pair<int, int>> v;
queue<pair<int, int>> bfsQueue;
int N, A, B;

bool isInClosedSection(int num)
{
	for (int i = 0; i < v.size(); i++)
	{
		if (num >= v.at(i).first && num <= v.at(i).second)
		{
			return true;
		}
	}
	return false;
}

void bfs()
{
	bool isFind = false;
	bfsQueue.push(pair(0, 0));
	isVisited[0] = 0;
	while (!bfsQueue.empty())
	{
		pair<int, int> front = bfsQueue.front();
		if (front.first == N)
		{
			isFind = true;
			cout << front.second << "\n";
			return;
		}
		if (front.first + A <= N && !isInClosedSection(front.first+A) && isVisited[front.first+A] == false)
		{
			isVisited[front.first + A] = true;
			bfsQueue.push(pair(front.first + A, front.second + 1));
		}
		if (front.first + B <= N && !isInClosedSection(front.first+B) && isVisited[front.first + B] == false)
		{
			isVisited[front.first + B] = true;
			bfsQueue.push(pair(front.first + B, front.second + 1));
		}
		bfsQueue.pop();
	}
	cout << -1 << "\n";
}

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

	int M, start, end;
	cin >> N >> M >> A >> B;
	isVisited = new bool[N + 1];
	for (int i = 0; i < N + 1; i++)
	{
		isVisited[i] = false;
	}
	for (int i = 0; i < M; i++)
	{
		cin >> start >> end;
		v.push_back(pair(start, end));
	}
	bfs();
	return 0;
}