백준 16965

문제

전체 쿼리의 수(구간의 최대 수)가 100 이하라는 전제로 모든 구간에 대한 BFS를 진행함으로서 이 문제를 해결할 수 있다.

UnionFind로 풀이하다 실패했는데, 구간의 순서가 구간의 포함 여부에 영향을 미치므로 모든 구간의 포함 관계가 갱신되었을때 각각의 포함된 구간에 대한 UnionFind를 다시 수행해줘야 이 문제를 풀이할 수 있다. 그러므로 단순한 BFS로 문제를 재구성했다.

 

결국 완전탐색으로 풀이해야하므로 2 a b에 대한 입력이 왔을때 a 구간에서부터 시작해서 이동할 수 있는 모든 구간에 대해 탐색하면서 이동할 수 있는 구간을 기준으로 다시 BFS를 진행하여 결국 b 구간이 나오는지에 대한 여부만 확인하면 된다.

구간의 수를 N이라 하고, 2 a b라는 쿼리가 오는 경우를 M이라 할때, O(N*M) (N+M <=100)이므로 해결할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
int N;
vector<pair<int,int > >v;
int main() {
    cin>>N;
    for(int i=0; i<N; i++) {
        int a, b, c; cin>>a>>b>>c;
        if(a == 1) {
            v.push_back(make_pair(b, c));
        }else if(a == 2) {
            queue<int>q;
            int vis[101]={0};
            q.push(b-1);
            vis[b-1] = 1;
            while(!q.empty()) {
                int cur = q.front(); q.pop();
                for(int i=0; i<v.size(); i++) {
                   if((v[i].first < v[cur].first && v[cur].first < v[i].second) || (v[i].first < v[cur].second && v[cur].second < v[i].second)) {
                        if(vis[i] == 0) {
                            vis[i] = 1;
                            q.push(i);
                        }
                    }
                }
            }
            if(vis[c-1] == 1) cout<<"1\n";
            else cout<<"0\n";
        }
    }
}