AMC 8 · 2003 · #18

• 그림의 선분을 읽고, 각 점에 사라까지의 거리를 적습니다.
• 그림에서 사라와 바로 연결된 친구는 $8$ 명입니다 (그림의 점 표기로 $p$, $o$, $d$, $e$, $j$, $k$, $q$, $s$ — 거리 $1$).
• 왼쪽 아래의 삼각형 세 점 ($l$, $m$, $n$)은 자기들끼리만 닫힌 고리로 이어져 있어 사라의 부분과 연결이 없고, 왼쪽 위에는 선분이 하나도 없는 외톨이 점 ($a$)이 있습니다.

💡 주어진 그림에 "사라까지의 거리" 라벨을 얹는 순간, "누가 초대받는가?" 가 단순한 분류 작업이 됩니다.

• 거리 $2$ 인 점(친구의 친구)을 찾습니다.
• 각 거리 $1$ 친구에서 선분을 한 번 더 따라가 새 점을 모으면: $d \to b, c$ / $e \to f$ / $s \to r, t$ / $j \to i$.
• 거리 $2$ 집합은 $\{b, c, f, r, t, i\}$ 로 $6$ 명이고, 이들 모두 초대받습니다.

💡 직접 친구에서 선분 하나만큼 더 걸어가서 새로 만나는 점이 "친구의 친구" 입니다.

• "초대받지 못함" 을 두 묶음으로 쪼갭니다.
• 묶음 $A$: 사라에게 가는 경로가 아예 없는 점.
• 묶음 $B$: 사라와 같은 연결 성분이지만 거리가 $3$ 이상인 점.

💡 한 번에 세려 하지 말고, 겹치지 않는 두 묶음으로 나눠서 따로 세는 게 안전합니다.

• 묶음 $A$(연결되지 않은 점들)를 셉니다.
• 왼쪽 아래 삼각형 $l$-$m$-$n$ 이 $3$ 명, 왼쪽 위 외톨이 점 $a$ 가 $1$ 명.
• 합쳐서 $A = 4$.

💡 그래프의 다른 조각에 있는 점은 선분을 아무리 따라가도 사라에게 닿지 못하므로 모두 초대받지 못합니다.

• 묶음 $B$(사라의 성분 안에서 너무 먼 점들)를 셉니다.
• 사라의 네트워크를 가로지르는 긴 사슬 $e$-$f$-$g$-$h$-$i$-$j$ 를 봅시다.
• $e$ 와 $j$ 는 직접 친구(거리 $1$), $f$($e$ 옆)와 $i$($j$ 옆)는 거리 $2$.
• 가운데 두 점 $g$ 와 $h$ 는 거리 $3$ 으로 "너무 멉니다".
• 사라의 성분 안에 거리 $\ge 3$ 인 다른 점은 없습니다.
• 따라서 $B = 2$.

💡 사라에서 바깥으로 한 걸음씩 나가다 보면 사슬에서 "가까움" 라벨이 바닥나는 지점이 정확히 $g$, $h$ 입니다.

두 묶음을 더해 답을 냅니다.

💡 겹치지 않는 묶음은 그냥 더하면 됩니다 — 중복 걱정이 없습니다.

• 여집합으로 교차 검증합니다.
• 초대받는 사람: 거리 $1$ 이 $8$ 명, 거리 $2$ 가 $6$ 명, 합 $14$.
• 전체가 $20$ 이므로 초대받지 못함 $= 20 - 14 = 6$.
• 직접 센 값과 같습니다.

💡 "초대받음" 을 세서 $20$ 에서 빼는 것은 여집합 검산 — 직접 센 $6$ 을 확인해 줍니다.