Note
Set 자료구조를 활용하여 전염이나 확산 현상을 추적하는 기법에 대해 알아봅니다.
문제 상황
어떤 상태나 특성이 전염되거나 확산되는 상황을 추적해야 할 때가 있습니다.
예를 들어:
- 무지개 댄스를 추는 사람이 다른 사람을 만나면 그 사람도 무지개 댄스를 배우게 됨
- 바이러스가 감염된 사람과 접촉한 사람도 감염됨
- 정보가 전달된 사람과 만난 사람도 정보를 얻게 됨
이런 문제를 해결하기 위해 Set 자료구조를 활용할 수 있습니다.
전염/확산 추적 알고리즘
핵심 아이디어
- 상태를 가진 집합 유지: 특정 상태(전염, 감염, 정보 보유 등)를 가진 항목들을 Set에 저장합니다.
- 접촉 시 상태 전파: 두 항목이 접촉했을 때, 둘 중 하나라도 Set에 있으면 둘 다 Set에 추가합니다.
- 최종 집계: 모든 접촉이 끝난 후 Set의 크기를 구하면 최종적으로 상태를 가진 항목의 수를 알 수 있습니다.
알고리즘 흐름
1. 초기 상태를 가진 항목들을 Set에 추가
2. 각 접촉 기록을 순회:
- 접촉한 두 항목 중 하나라도 Set에 있으면:
* 두 항목 모두 Set에 추가 (상태 전파)
3. 최종적으로 Set의 크기를 출력
기본 구현
# 초기 상태를 가진 항목 설정
infected = set(["초기_항목"])
# 접촉 기록 처리
for contact in contacts:
person1, person2 = contact
# 둘 중 하나라도 상태를 가지고 있으면
if person1 in infected or person2 in infected:
# 둘 다 상태를 가지게 됨
infected.add(person1)
infected.add(person2)
# 최종 결과
print(len(infected))구현 포인트
- 초기 상태 설정: 문제에서 주어진 초기 상태를 가진 항목들을 Set에 추가합니다.
- 상태 전파 조건: 접촉한 두 항목 중 하나라도 Set에 있으면 둘 다 추가합니다.
- Set의 자동 중복 제거: 같은 항목이 여러 번 추가되어도 Set은 자동으로 중복을 제거합니다.
시간 복잡도 분석
- 각 접촉 처리: O(1) - Set의
in연산과add연산이 모두 O(1) - 전체 시간 복잡도: O(N) (N은 접촉 기록 개수)
Set을 사용하지 않고 리스트로 상태를 체크한다면 O(N²)이 되지만, Set을 사용하면 O(N)으로 최적화됩니다.
그래프 관점에서의 이해
이 문제는 그래프 이론의 관점에서 볼 수도 있습니다:
- 노드: 각 항목(사람, 개체 등)
- 엣지: 접촉 관계
- 초기 노드: 초기 상태를 가진 항목
- 연결된 컴포넌트: 초기 노드와 연결된 모든 노드가 상태를 가지게 됨
하지만 이 알고리즘은 그래프를 명시적으로 구성하지 않고, Set을 이용하여 간단하게 해결할 수 있습니다.
활용 예시
이 패턴은 다음과 같은 상황에서 유용합니다:
- 전염병 확산 추적
- 정보 전파 시뮬레이션
- 소셜 네트워크에서의 영향력 확산
- 연결된 컴포넌트의 크기 계산 (간단한 경우)
관련 문제
- BOJ 26069: 붙임성 좋은 총총이 - Set을 이용한 전염/확산 추적 문제