좌표 평면 위에 놓인 점들의 목록과 숫자 k가 주어졌다고 가정해 봅시다. 각 점은 데카르트 좌표(Cartesian coordinate)를 나타내는 (x, y) 형태입니다. 두 점 p1과 p2 사이의 유클리드 거리가 k 이하일 때, 이 두 점을 같은 그룹으로 묶을 수 있습니다. 이때 구해야 하는 것은 서로 겹치지 않는 분리된 그룹(disjoint groups)의 총 개수입니다.
예를 들어 입력이 다음과 같다면,
points = [[2, 2], [3, 3], [4, 4], [11, 11], [12, 12]], k = 2
출력은 2가 됩니다. [2, 2], [3, 3], [4, 4]는 서로 인접해 있어 하나의 그룹을 이루고, [11, 11]과 [12, 12] 역시 서로 가까워 별도의 그룹을 형성하기 때문입니다.
접근 방법: DFS로 연결 요소 찾기
이 문제는 그래프 이론의 연결 요소(Connected Component) 개념으로 해결할 수 있습니다. 각 점을 그래프의 정점(vertex)으로 보고, 유클리드 거리가 k 이하인 두 점 사이를 간선(edge)으로 연결하면, 전체 그래프에서 연결 요소의 개수가 곧 그룹의 개수가 됩니다.
알고리즘 단계
- 정점 i를 받아 탐색하는 dfs() 함수를 정의합니다.
- i가 이미 방문한(seen) 정점이라면 즉시 반환합니다.
- i를 seen 집합에 추가합니다.
- adj[i]에 있는 모든 이웃 정점 nb에 대해 dfs(nb)를 재귀 호출합니다.
메인 로직
- adj : 인접 리스트를 담는 맵(map)을 생성합니다.
- n : 점 목록의 크기를 저장합니다.
- 모든 점 쌍 (i, j)에 대해 두 점 사이의 유클리드 거리가 k 이하인지 확인하고, 조건을 만족하면 adj[i]에 j를, adj[j]에 i를 추가하여 양방향 간선을 만듭니다.
- seen : 새로운 집합(set)을 생성합니다.
- ans : 그룹 개수를 세는 변수로 0으로 초기화합니다.
- 0부터 n까지 반복하면서 아직 방문하지 않은 정점 i를 만나면 ans를 1 증가시키고 dfs(i)를 호출합니다.
- 최종적으로 ans를 반환합니다.
Python 구현 예제
from collections import defaultdict
class Solution:
def solve(self, points, k):
adj = defaultdict(list)
n = len(points)
for j in range(n):
for i in range(j):
x1, y1 = points[i]
x2, y2 = points[j]
if (x1 - x2) ** 2 + (y1 - y2) ** 2 <= k ** 2:
adj[i].append(j)
adj[j].append(i)
seen = set()
def dfs(i):
if i in seen:
return
seen.add(i)
for nb in adj[i]:
dfs(nb)
ans = 0
for i in range(n):
if i not in seen:
ans += 1
dfs(i)
return ans
ob = Solution()
points = [
[2, 2],
[3, 3],
[4, 4],
[11, 11],
[12, 12]
]
k = 2
print(ob.solve(points, k))입력
[[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]],2
출력
2
복잡도 분석
- 시간 복잡도: 모든 점 쌍을 비교하는 데 O(n²)이 걸리고, DFS 탐색에도 O(n²)이 소요되므로 전체 시간 복잡도는 O(n²)입니다.
- 공간 복잡도: 인접 리스트와 방문 집합을 저장하는 데 최대 O(n²)의 공간이 필요합니다.
참고로 코드에서는 제곱근 계산을 피하기 위해 실제 거리 대신 거리의 제곱((x1-x2)² + (y1-y2)²)을 k²와 직접 비교합니다. 이렇게 하면 부동소수점 오차 없이 정확한 비교가 가능하고 연산 성능도 함께 향상됩니다.