[백준 2533번] 사회망 서비스(SNS) (Python3)

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())

graph = [[] for i in range(N)]
nodes = [0]*N
for i in range(N-1):
  x,y = map(int,input().split())
  graph[x-1].append(y-1)
  graph[y-1].append(x-1)
  nodes[x-1] += 1
  nodes[y-1] += 1

offlist = deque()
onlist = deque()
check = [0]*N

for i in range(N):
  if nodes[i] == 1:
    offlist.append(i)

result = 0
cnt = 0
while True:
  if cnt == N:
    break
  while offlist:
    now = offlist.pop()
    if check[now]:
      continue
    check[now] = 1
    cnt += 1
    for next in graph[now]:   
      nodes[next] -= 1
      if check[next]:
        continue
      if nodes[next] == 0:
        result += 1
        check[next] = 1
        cnt += 1
        continue
      onlist.append(next)
      
  if cnt == N:
    break
  while onlist:
    now = onlist.pop()
    if check[now]:
      continue
    result += 1
    check[now] = 1
    cnt += 1
    for next in graph[now]:
      nodes[next] -= 1
      if check[next]:
        continue
      if nodes[next] == 1:
        offlist.append(next)
print(result)

 

솔직히 이 문제는 어떻게 맞춘지 모르겠다.

내가 풀면서도 "아 이건 아닌거같은데" "분명히 틀릴텐데 어디서부터 고쳐야되나..." 하고 제출했는데 맞았다.

 

일단 기본적인 알고리즘은

1. 모든 노드에 대해서 친구 숫자가 몇명인지를 체크한다 (nodes 리스트)

2. 친구가 한명인 노드, 즉 트리의 가장 끝의 유저는 모두 일반인이라고 가정한다. 이 노드를 offlist에 넣는다.

3. 일반인과 연결된 친구는 무조건 얼리어답터여야 하므로 onlist에 모두 넣는다.

4. 이 과정에서 이미 체크한 노드를 제거한다고 생각하고, 체크한 노드와 연결된 노드는 친구의 숫자를 한명씩 줄인다.

5. 친구가 한명인 노드에 대해서 offlist에 넣고 2~4 과정을 반복한다.

 

쉽게 말하면 트리의 가장자리부터 한 층씩 올라올때마다 일반인, 얼리어답터, 일반인, 얼리어답터가 반복된다는 매커니즘이다.

 

이 경우가 최소라는걸 직감적으로는 알았는데 증명하지는 못해서 뭔가 반례가 있을줄 알았는데 맞은걸 보니 맞는 풀이인 것 같다.

 

 

오늘의 교훈) 트리 알고리즘에 좀 더 익숙해지자