[c++] 백준 10216 - Count Circle Groups(BFS, DFS)

0. [c++] 백준  -

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

1. 풀이

문제의 첫줄부터 매우 의심이 차올랐던 문제였지만, 일단 신경을 끄고 문제를 풀어보았다.

BFS와 DFS를 두가지 다 활용해서 문제를 풀어보았는데, 자신과 붙어있는 노드를 확정시키기 어려워 범위 전체를 순환시켜버렸다.

허나 이 때문에 시간은 길어져 버렸다.

이를 어떻게 조금만 아이디어가 나온다면 이를 해결할 수 있을 것 같은데....

뭐 하튼 해결을 하기는 하였다.

근데, BFS랑 DFS 바꿔서 만들어져있네...

2. 소스코드

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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104

#include<iostream> #include<vector> #include<math.h> #include<cstring>    //memset()을 활용하기 위해서 #include<queue>   using namespace std;   //pair<int, int>에는 x,y를 담고 뒤에는 통신 범위를 담는다. vector<pair<pair<int, int>, int> > enemy; bool visited[3000]; int N; queue<int> nextFind;   bool calcDistance(pair<pair<int, int>, int>& here, pair<pair<int, int>, int>& there) {     int x = here.first.first - there.first.first;     int y = here.first.second - there.first.second;     x = x*x; y = y*y;     //cout << "sqrt = " << sqrt(x + y) << " x = :" << x << " y = " << y <<endl;     double ret = sqrt(x + y) - here.second - there.second;     //cout << "ret : " << ret << endl;     if (ret <= 0)         return true;          return false; }   //BFS void BFS(pair<pair<int, int>, int>& here, int hereOrder) {     //기저 사례:이미 방문하였다면 탐색을 종료한다.     if (visited[hereOrder])         return;     visited[hereOrder] = true;     for (int i = 0; i < N; i++) {         //통신 범위 내에 존재하면, BFS로 탐색을 들어간다.         if (!visited[i])             if (calcDistance(here, enemy[i]))                 BFS(enemy[i], i);     } }   //DFS void DFS(pair<pair<int, int>, int>& here, int hereOrder) {     for (int i = 0; i < N; i++) {         //통신 범위 내에 존재하면, 큐에 추가한다.         if (!visited[i])             if (calcDistance(here, enemy[i])) {                 nextFind.push(i);                 visited[i] = true;             }     } }       int main() {     int T, x,y,range;     cin >> T;     while (T--) {         cin >> N;         enemy.clear();         for (int i = 0; i < N; i++) {             cin >> x >> y >> range;             enemy.push_back({ {x,y},range });         }         //BFS를 활용해서 해결하자         int count = 0;         memset(visited, false, sizeof(visited));         //for (int i = 0; i < N; i++) {         //    if (!visited[i]) {         //        //cout << "here : " << i << endl;         //        BFS(enemy[i], i);         //        count++;         //    }         //}                  //DFS를 활용해보자         while (1) {                          if (nextFind.empty()) {                 for (int i = 0; i < N; i++) {                     if (!visited[i]) {                         nextFind.push(i);                         visited[i] = true;                         count++;                         break;                     }                 }                 if (nextFind.empty())                     break;             }             DFS(enemy[nextFind.front()], nextFind.front());             nextFind.pop();         }         cout << count << endl;       }                     return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!