[ 백준 / G3 / 파이썬 Python ] 2533번 사회망 서비스(SNS)

링크 : https://www.acmicpc.net/problem/2533

2533번: 사회망 서비스(SNS)

 

코드

---

from collections import defaultdict

n = int(input())
link = defaultdict(list)
for _ in range(n-1):
    u,v = map(int,input().split())
    link[u].append(v)
    link[v].append(u)

leaf = [i for i in range(1,n+1) if len(link[i]) == 1]
answer = [0] * (n+1)
while leaf:
    leaf_node = leaf.pop()
    if not link[leaf_node]: continue
    adapter = link[leaf_node][0]
    for b in link[adapter]:
        link[b].remove(adapter)
        if len(link[b]) == 1: leaf.append(b)
    answer[adapter] = 1
    link[adapter] = []

print(sum(answer))

 

사용 알고리즘

---

" 위상 정렬 "

 

풀이

---

 

문제를 해결하는 아이디어는 다음과 같다.

1. 단말노드(a)는 어댑터가 될 수 없다.
2. 단말노드와 연결된 노드(b)는 반드시 얼리 어댑터이다.
3. b가 얼리 어댑터가 됨으로써 b와 연결된 노드 중 단말노드가 된 노드를 통해 다시 과정을 반복한다.

따라서 이 문제의 핵심은 단말노드를 찾고 업데이트하는 것이다.

 

초기의 단말노드 리스트는 다음과 같다.

leaf = [i for i in range(1,n+1) if len(link[i]) == 1]

친구 관계에서 친구 수가 1명인 사람은 단말 노드가 된다.

 

다음은 단말노드에 연결된 노드를 어댑터로 만들고 그 어댑터와 연결된 노드들에서 단말노드를 업데이트하는 과정이다.

while leaf:
    leaf_node = leaf.pop()
    if not link[leaf_node]: continue
    adapter = link[leaf_node][0]
    for b in link[adapter]:
        link[b].remove(adapter)
        if len(link[b]) == 1: leaf.append(b)
    answer[adapter] = 1
    link[adapter] = []

b는 어댑터와 연결된 노드이며 더 이상 탐색할 필요가 없는 어댑터를 친구목록에서 삭제한다.

어댑터를 친구목록에서 지움으로써 친구 수가 1이 되면 단말노드로 추가해준다.

어댑터는 더 이상 탐색할 필요가 없기 때문에 모든 친구 링크를 지워준다.

---

비슷한 문제로 프로그래머스의 등대 문제가 있다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/133500

프로그래머스

 

from collections import defaultdict

n = int(input())
link = [list(map(int,input().split())) for _ in range(n-1)]
answer = [0] * (n+1)
while 1:
    graph = defaultdict(list)
    for a,b in ((u,v) for u,v in link if answer[u]+answer[v] == 0):
        graph[a].append(b)
        graph[b].append(a)

    if not graph: break

    for k,v in graph.items():
        if len(v) == 1 and answer[k] == 0:
            answer[v[0]] = 1
            answer[k] = 2
print(answer.count(1))

이 문제에서는 연결관계를 고정하고 불을 켠 등대와 연결된 노드는 모두 제외하면서 그래프를 매번 새로 만들게 된다.

등대 문제와 비슷하게 코드를 작성했더니 시간초과가 발생하였다.

 

등대 문제에서는 n이 10만이었기에 통과가 가능했지만 이번 문제에서는 n이 100만이 되어서 시간초과로 통과하지 못하였다.