반응형

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

 

16965번: 구간과 쿼리

N개의 쿼리가 주어졌을 때, 쿼리를 수행해보자. 쿼리는 총 2가지 종류가 있고 아래와 같다. 가장 처음에 집합에는 아무것도 없다. 1 x y (x < y): 새로운 구간 (x, y)를 집합에 추가한다. 구간의 크기

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. vector<pair<int, int>> list를 만들어 1번 쿼리가 입력될 때마다 list에 {x, y}를 push 합니다.

 

2. 2번 쿼리가 입력될 때마다 bfs를 돌려 a부터 b까지 이동하는 경로가 있다면 1을 아니라면 0을 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N;
vector<pair<int, int>> list;
 
bool bfs(int a, int b)
{
    int visited[101] = { 0 };
 
    queue<int>q;
 
    q.push(a - 1);
    visited[a - 1] = 1;
 
    while (!q.empty()) {
        const int cur = q.front();
        const int x = list[cur].first;
        const int y = list[cur].second;
        q.pop();
 
        if (cur == b - 1) {
            return true;
        }
 
        for (int i = 0; i < list.size();i++) {
            if (visited[i] != 1 && ((list[i].first < x && x < list[i].second) || (list[i].first < y && y < list[i].second))) {
                visited[i] = 1;
                q.push(i);
            }
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int x, y;
            cin >> x >> y;
            list.push_back({ x,y });
        }
        else {
            int a, b;
            cin >> a >> b;
 
            if (bfs(a, b)) cout << 1;
            else cout << 0;
            cout << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
[ 백준 ] 3067번 - Coins (C++)  (0) 2023.08.18
[ 백준 ] 20007번 - 떡 돌리기 (C++)  (0) 2023.08.16
[ 백준 ] 2224번 - 명제 증명 (C++)  (0) 2023.08.15
[ 백준 ] 20182번 - 골목 대장 호석 - 효율성 1 (C++)  (0) 2023.08.14

+ Recent posts

티스토리툴바