[백준/BOJ] 백준 16965번 : 구간과 쿼리

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

16965번: 구간과 쿼리

 

새로운 구간을 집합에 추가하는 쿼리일 때, 이전에 들어왔던 구간들과 이동이 가능한지 확인하여 만약 이동이 가능하다면 그래프로 연결했고, 구간 사이 이동이 가능한지 확인하는 쿼리일 때는 만들어 놓은 그래프를 이용해 두 구간 사이 탐색으로 도달이 가능한지 확인해서 문제를 해결했다.

 

코드

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

int n;
vector<pair<int, int>> range;
vector<int> result;

vector<int> adj[105];
vector<int> visited(105, 0);

void init() {
	for (int i = 0; i < 105; i++) {
		visited[i] = 0;
	}
}

bool dfs(int here, int dest) {

	visited[here] = 1;

	if (here == dest) {
		return true;
	}

	int ret = false;

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];

		if (visited[there] == 0) {
			ret |= dfs(there, dest);
		}
	}

	return ret;
}

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int query, a, b;

		cin >> query >> a >> b;

		if (query == 1) { //범위 추가일때

			range.push_back(make_pair(a, b));

			//이전에 들어왔던 구간이랑 그래프를 연결
			for (int r = 0; r < range.size() - 1; r++) {
				int u = range.size() - 1;
				int v = r;
				int x1 = range[u].first;
				int y1 = range[u].second;
				int x2 = range[v].first;
				int y2 = range[v].second;

				//u에서 v로 갈 수 있는지 확인
				if ((x2 < x1 && x1 < y2) || (x2 < y1 && y1 < y2)) {
					adj[u].push_back(v);
				}


				//v에서 u로 갈 수 있는지 확인
				if ((x1 < x2 && x2 < y1) || (x1 < y2 && y2 < y1)) {
					adj[v].push_back(u);
				}
			}

		}

		else { //이동할 수 있는지 확인할때

			init();

			//구간 사이의 이동이 가능한지 탐색
			if (dfs(a - 1, b - 1)) {
				result.push_back(1);
			}
			else {
				result.push_back(0);
			}

		}

	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

	return 0;
}