[백준] 10216.cpp : Count Circle Groups

www.acmicpc.net/problem/10216

10216번: Count Circle Groups

#include <iostream>
#include <vector>
#define pow2(n) ((n)*(n))
using namespace std;

// 각 진영을 하나의 객체로 취급
struct Point
{
  int x;
  int y;
  int r;
  // 서로 연결되어 있는 노드 정보들
  vector<Point*> nodes;
  // dfs 탐색 시 체크 여부
  bool checked = false;

  // dfs 탐색 시 호출되는 함수
  void changeState()
  {
    // 이미 체크되었던 진영이면 그냥 끝
    if(checked) return;
    checked = true;
    // 나에게 연결되어 있는 진영들을 다 체크해준다
    for(int i = 0 ; i < nodes.size() ; i++)
    {
      nodes[i]->changeState();
    }
  }
};


int main(void)
{
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);

  int t;
  cin >> t;
  for(int tc = 0 ; tc < t ; tc++)
  {
    int n;
    int number = 0;
    cin >> n;

    // 각 진영들에 대한 정보
    vector<Point> v;
    v.reserve(n); // n개
    int x, y, r;
    // 진영 정보 넣어주고
    for(int i = 0 ; i < n ; i++)
    {
      cin >> x >> y >> r;
      v.emplace_back(Point{x, y, r});
    }
    // 각 진영들을 서로 연결해준다
    for(int i = 0 ; i < v.size() ; i++)
    {
      for(int j = i + 1 ; j < v.size() ; j++)
      {
        if(pow2(v[i].x - v[j].x) + pow2(v[i].y - v[j].y) <= pow2(v[i].r + v[j].r))
        {
          v[i].nodes.push_back(&v[j]);
          v[j].nodes.push_back(&v[i]);
        }
      }
    }
    // dfs 탐색 시작, 연결되어있는 진영별로 하나씩 카운트
    for(int i = 0 ; i < v.size() ; i++)
    {
      if(v[i].checked == false)
      {
        v[i].changeState();
        number++;
      }
    }

    cout << number << '\n';
  }
}

 

[Approach]

1. DFS 사용하여 그룹별로 체크해나가면서 풀면 될 것 같다. 5000 * 5000 을 다 검사하면 시간초과가 날까?

     -> 배열 인덱스 잘못 주어서 런타임에러 1번, 배열 2500만개에서 메모리 초과 3번. 배열 전부 검사는 답이 아닌 것 같다.

2. 서로 노드를 만들어서 연결해주는 방식으로 했는데 이번엔 시간초과가 난다.

     어찌저찌 바꿔줘도 시간초과 3스택.

3. 벡터를 처음에 n 개 만들고 그 뒤로 n 개를 더 추가해서 괜히 갯수만 두배로 늘려서 시간초과가 난 것 같다. 열받네

     정신 똑바로 차리자 진짜.

 

[Point]

1. 대부분 2차원배열 선언해서 푸신 것 같다. 원리 자체는 비슷하다.

2. 맞아놓고 다시 보면 정말 간단한 풀이법인데, 왜 푸는데에는 이렇게 오래 걸리고, 접근을 잘못 하는건지... 문제를 더 많이 풀자.