[BaekJoon] 10216번 : Count Circle Groups

10216번 : Count Circle Groups

적군의 진영을 BFS 로 탐색하면서 통신이 되는 경우 연결해 주면 된다.

방문 하지 않은 진영을 시작으로 BFS 를 수행하고, BFS 를 수행 한 횟수가 그룹의 개수가 된다.

union-find 를 사용하면 BFS 보다 시간을 단축 할 수 있다.

하지만.. 어떻게 적용을 시켜야 할지 아직 모르겠다.

복습을 할 때는 union-find 를 사용해 풀어봐야겠다.

[21.03.11] 복습

union-find 를 적용해 풀어보았다. 기존의 코드는 14000ms 가 걸렸던 반면 지금은 2100ms 가 소요된다.

처음엔 가능한 모든 간선을 만든 뒤 그 간선의 정보를 가지고 MST 를 만드는 방식으로 했다.

하지만 시간초과가 발생했고, 가능한 모든 간선을 만들지 않고 노드 정보만을 가지고 union-find 를 해야했다.

그런데 계속 생각해보니 애초에 간선을 만들 이유가 없었다.

노드의 정보만으로 두 노드가 연결될지 안될지를 정할 수 있었기 때문이다.

노드 정보를 x_pos, y_pos, radius 로 나누어 저장하는 방법과

nodes 리스트에 한 번에 저장한 뒤 가져다 쓰는 방법은 무려 5000ms 나 차이가 난다.

---

[21.03.11] 복습

import sys


def find_parent(parent, node):
    if parent[node] != node:
        parent[node] = find_parent(parent, parent[node])

    return parent[node]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


def solution():
    answer = node_cnt
    parent = [i for i in range(node_cnt)]

    for i in range(node_cnt):
        for j in range(i + 1, node_cnt):
            x_dif = x_pos[i] - x_pos[j]
            y_dif = y_pos[i] - y_pos[j]
            dist = radius[i] + radius[j]

            if (x_dif ** 2) + (y_dif ** 2) <= dist ** 2:
                if find_parent(parent, i) != find_parent(parent, j):
                    union_parent(parent, i, j)
                    answer -= 1

    return answer


if __name__ == "__main__":
    testcase = int(input())

    for _ in range(testcase):
        node_cnt = int(input())
        x_pos, y_pos, radius = [], [], []
        for _ in range(node_cnt):
            x, y, r = map(int, sys.stdin.readline().rsplit())
            x_pos.append(x)
            y_pos.append(y)
            radius.append(r)

        print(solution())

---

import sys
from collections import deque


def BFS(visit, start):
	queue = deque([nodes[start]])
	visit[start] = True

	while queue:
		x1, y1, r1 = queue.popleft()

		for idx, node in enumerate(nodes):
			if not visit[idx]:
				x2, y2, r2 = node
				dist = (x1 - x2) ** 2 + (y1 - y2) ** 2
				if dist <= (r1 + r2) ** 2:
					visit[idx] = True
					queue.append(node)


def solution():
	visit = [False] * node_cnt
	BFS_cnt = 0

	for idx, node in enumerate(nodes):
		if not visit[idx]:
			BFS(visit, idx)
			BFS_cnt += 1

	return BFS_cnt


if __name__ == "__main__":
	testcase = int(input())

	for _ in range(testcase):
		node_cnt = int(input())
		nodes = []
		for _ in range(node_cnt):
			x, y, r = map(int, sys.stdin.readline().rsplit())
			nodes.append([x, y, r])

		print(solution())