피드로 돌아가기
Dev.toBackend
원문 읽기
DFS 기반 그래프 탐색을 통한 Connected Components 분리 및 최적화
Leetcode 547 solving with intuition - 6/8/26
AI 요약
Context
도시 간 연결 상태를 나타내는 인접 행렬에서 독립된 주(Province)의 개수를 파악하는 문제. 단순 행 합계 계산 방식으로는 서로 다른 독립 클러스터가 존재하는 복잡한 그래프 구조를 식별하지 못하는 한계 존재.
Technical Solution
- 그래프의 정점과 간선 관계를 분석하여 Connected Components를 찾는 문제로 정의
- Depth-First Search(DFS) 알고리즘을 채택하여 연결된 모든 정점을 단일 그룹으로 묶는 탐색 구조 설계
- Visited Array를 도입하여 중복 방문을 방지하고 탐색 효율성 확보
- 외부 헬퍼 함수를 통한 반복 스캔 방식을 제거하고, 단일 루프 내에서 미방문 정점 발견 시에만 DFS를 트리거하는 최적화 수행
- 재귀적 호출을 통해 연결된 모든 노드를 방문 처리함으로써 Province 카운트의 정확도 향상
실천 포인트
1. 연결성 분석 문제 발생 시 단순 합계가 아닌 Graph Traversal 알고리즘 적용 검토
2. 불필요한 전체 상태 스캔을 방지하기 위한 Visited State 관리 전략 수립
3. 재귀 호출 시 기저 조건과 방문 여부 체크를 통한 무한 루프 방지 로직 구현