2533. [Python]사회망 서비스

1. 문제

 

 

2. 접근 방법

 

• 시간 제한: 3초
• 메모리 제한: 256MB
• 트

 

3. 파이썬 코드

 

import sys
# 많은 인풋 처리
input = sys.stdin.readline

N = int(input())
# 그래프 연결
graph = [ [] for _ in range(N+1)]
# 방문 처리
visited = [ 0 for _ in range(N+1) ]
# 양방향 그래프
for _ in range(N-1):
    S,E = map(int,input().split())
    graph[S].append(E)
    graph[E].append(S)
# 리프 노드 저장
leaf_node = []
# 리프 노드에 값 저장
for i in range(1,N+1):
    if len(graph[i]) == 1:
        leaf_node.append(i)
# 리프노드가 없을때까지 반복
while leaf_node:
    # 뽑아냄
    next = leaf_node.pop()
    # 연결된 그래프 노드 탐색
    for i in graph[next]:
        # 방문 했으면 무시
        if visited[i] == 1:
            continue
        # 그래프와 연결된 값들 순회
        for j in graph[i]:
            # j 노드와 i 노드의 연결을 제거
            graph[j].remove(i)
            # 제거한 노드와 개수가 1개인 경우 => 리프 노드
            if len(graph[j]) == 1:
                # 리프 노드에 값 추가
                leaf_node.append(j)
        # i 노드 방문 처리
        visited[i] = 1
        # i 노드와 연결된 그래프 초기화 위에서 연결을 제거했기 때문에
        graph[i] = []

print(sum(visited))

 

4. 문제를 풀고난 후 생각

 

• '그래프가 트리인 경우, 즉 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우만 고려' 이기 때문에 트리에 사이클이 없다
• 제일 먼저 리프노드들만 골라서 리스트에 값을 저장해준다.
• 리프 노드부터 역으로 올라가는 것을 진행한다.

리프 노드 저장

• 리프 노드에서 연결된 노드들을 모두 순회

다음 리프 노드 저장

• 다음 리프노드를 순회하며 이전 리프 노드 삭제 및 리프노드와 연결된 노드를 초기화
• 위와 같은 과정을 끝까지 반복하면 visited 에 방문된 개수를 체크하면 최소 몇개의 노드를 얼리 아답터로 정해야 하는지 알 수 있다.

5. 문제를 푸는데 도움이 되는 지식

 

• 트리