Note
확산 추적 기법을 활용하여 해결하는 문제입니다.
문제
총총이는 친구 곰곰이의 소개로 제2회 곰곰컵에 출연할 기회를 얻었다!
총총이는 자신의 묘기인 무지개 댄스를 선보여, 여러분의 환심을 사려 한다. 이 댄스는 중독성이 강하기 때문에, 한번 보게 된 사람은 모두 따라 하게 돼버린다.
사람들이 만난 기록이 시간 순서대로 개 주어진다. (총총이는 토끼이지만 이 문제에서는 편의상 사람이라고 가정한다.)
무지개 댄스를 추지 않고 있던 사람이 무지개 댄스를 추고 있던 사람을 만나게 된다면, 만난 시점 이후로 무지개 댄스를 추게 된다.
기록이 시작되기 이전 무지개 댄스를 추고 있는 사람은 총총이 뿐이라고 할 때, 마지막 기록 이후 무지개 댄스를 추는 사람이 몇 명인지 구해보자!
문제 링크: https://www.acmicpc.net/problem/26069
입력
첫 번째 줄에는 사람들이 만난 기록의 수 이 주어진다.
두 번째 줄부터 개의 줄에 걸쳐 사람들이 만난 기록이 주어진다. 번째 줄에는 번째로 만난 사람들의 이름 와 가 공백을 사이에 두고 주어진다. 와 는 숫자와 영문 대소문자로 이루어진 최대 길이 의 문자열이며, 서로 같지 않다.
총총이의 이름은 ChongChong으로 주어지며, 기록에서 1회 이상 주어진다.
동명이인은 없으며, 사람의 이름은 대소문자를 구분한다. (ChongChong과 chongchong은 다른 이름이다.)
출력
마지막 기록 이후 무지개 댄스를 추는 사람의 수를 출력하라.
예제
예제 입력 1:
12
bnb2011 chansol
chansol chogahui05
chogahui05 jthis
jthis ChongChong
jthis jyheo98
jyheo98 lms0806
lms0806 pichulia
pichulia pjshwa
pjshwa r4pidstart
r4pidstart swoon
swoon tony9402
tony9402 bnb2011
예제 출력 1:
10
문제 분석
이 문제는 확산 추적 기법을 직접 적용할 수 있는 문제입니다.
핵심 이해
- 초기 상태: ChongChong만 무지개 댄스를 추고 있음
- 전파 규칙: 무지개 댄스를 추는 사람과 만나면 그 사람도 무지개 댄스를 추게 됨
- 목표: 최종적으로 무지개 댄스를 추는 사람의 수
예제 1 상세 분석
초기: dancing = {"ChongChong"}
bnb2011 chansol → 둘 다 dancing에 없음 (변화 없음)
chansol chogahui05 → 둘 다 dancing에 없음 (변화 없음)
chogahui05 jthis → 둘 다 dancing에 없음 (변화 없음)
jthis ChongChong → ChongChong이 dancing에 있음!
→ jthis 추가: dancing = {"ChongChong", "jthis"}
jthis jyheo98 → jthis가 dancing에 있음!
→ jyheo98 추가: dancing = {"ChongChong", "jthis", "jyheo98"}
jyheo98 lms0806 → jyheo98이 dancing에 있음!
→ lms0806 추가: dancing = {...}
lms0806 pichulia → lms0806이 dancing에 있음!
→ pichulia 추가
pichulia pjshwa → pichulia가 dancing에 있음!
→ pjshwa 추가
pjshwa r4pidstart → pjshwa가 dancing에 있음!
→ r4pidstart 추가
r4pidstart swoon → r4pidstart가 dancing에 있음!
→ swoon 추가
swoon tony9402 → swoon이 dancing에 있음!
→ tony9402 추가
tony9402 bnb2011 → tony9402가 dancing에 있음!
→ bnb2011 추가
최종: dancing = {"ChongChong", "jthis", "jyheo98", "lms0806", "pichulia",
"pjshwa", "r4pidstart", "swoon", "tony9402", "bnb2011"}
결과: 10명
해결 방법
확산 추적 알고리즘을 사용합니다:
- 초기에 ChongChong을 Set에 추가합니다.
- 각 접촉 기록을 순회하면서, 두 사람 중 하나라도 Set에 있으면 둘 다 Set에 추가합니다.
- 최종적으로 Set의 크기를 출력합니다.
코드 구현
N = int(input())
dancing = set(["ChongChong"])
for i in range(N):
names = input().split(" ")
person1, person2 = names[0], names[1]
# 둘 중 하나라도 무지개 댄스를 추고 있으면
if person1 in dancing or person2 in dancing:
# 둘 다 무지개 댄스를 추게 됨
dancing.add(person1)
dancing.add(person2)
print(len(dancing))개선된 코드 (더 명확한 버전)
N = int(input())
dancing = set(["ChongChong"])
for i in range(N):
person1, person2 = input().split()
# 둘 중 하나라도 무지개 댄스를 추고 있으면
if person1 in dancing or person2 in dancing:
dancing.add(person1)
dancing.add(person2)
print(len(dancing))코드 설명
-
초기화:
dancingSet에 “ChongChong”을 초기값으로 추가합니다. -
접촉 처리:
- 두 사람이 만났을 때,
person1 in dancing or person2 in dancing으로 둘 중 하나라도 무지개 댄스를 추고 있는지 확인합니다. - 조건이 참이면 둘 다 Set에 추가합니다.
- 두 사람이 만났을 때,
-
결과 출력: 최종적으로 Set의 크기를 출력합니다.
왜 이렇게 동작하는가?
- Set의 자동 중복 제거: 같은 사람이 여러 번 추가되어도 Set은 하나만 저장합니다.
- 상태 전파: 한 번 Set에 추가되면, 그 사람과 만나는 모든 사람도 Set에 추가됩니다.
- 순서 보장: 입력이 시간 순서대로 주어지므로, 순차적으로 처리하면 올바른 결과를 얻을 수 있습니다.
주의사항
Note
원래 제공된 코드에서는
dancing.__contains__(name)을 사용했는데, 이는name in dancing과 동일합니다.in연산자를 사용하는 것이 더 Pythonic하고 읽기 쉽습니다.
시간 복잡도
- 각 접촉 처리: O(1) - Set의
in연산과add연산이 모두 O(1) - 전체 시간 복잡도: O(N) (N은 접촉 기록 개수)
Set을 사용하지 않고 리스트로 상태를 체크한다면 O(N²)이 되어 시간 초과가 발생할 수 있습니다.
그래프 관점에서의 이해
이 문제는 그래프 이론의 관점에서 볼 수도 있습니다:
- 노드: 각 사람
- 엣지: 사람들 간의 만남
- 초기 노드: ChongChong
- 연결된 컴포넌트: ChongChong과 연결된 모든 사람이 무지개 댄스를 추게 됨
하지만 이 알고리즘은 그래프를 명시적으로 구성하지 않고, Set을 이용하여 간단하게 해결할 수 있습니다.