백준-2533-사회망 서비스

문제

사회망 서비스

풀이

1. 문제조건 해석

   트리의 노드가 연속해서 선택되지 않는 경우가 없게끔 선택 하는 경우 중

   최소 경우의 수 구하는 문제

2. 알고리즘

   dp문제로 분류가 되어 있었으나, 나는 도저히 dp로는 못풀겠다. 다음 블로그를 참고하자

   나는 DFS로 해결했다. 해결하는 과정이 꽤 까다로워서 오래 걸렸다.

3. 코드

sfrom sys import setrecursionlimit, stdin
setrecursionlimit(1000000)
input = stdin.readline # 입력 시간 안줄여주면 시간초과 난다
n = int(input().rstrip())
tree = [[] for _ in range(n+1)] # 2차원 인접 리스트
for _ in range(n-1):
    n1, n2 = [int(x) for x in input().rstrip().split()]
    tree[n1].append(n2)
    tree[n2].append(n1) # 여기서 한쪽 노드만 인접하게 설정해줘서 계속 오답났다.

# DFS
# 1. 단말 노드이면 연결된 노드는 얼리어답터
# 2. 연결된 노드가 모두 얼리어답터 아니면 무조건 얼리어답터
early = set()
visited = set()
def dfs(n):
    global tree, early, visited
    visited.add(n)
    if len(tree[n]) <= 1: # 단말노드이다
        return True 
    for i in tree[n]:
        if not i in visited: # 양방향 그래프이므로 무한루프에 빠지지 않게끔
            if dfs(i):
                early.add(n)
            elif not i in early: # 연결된 노드가 얼리어답터 아니면
                early.add(n)
    return False # 단말노드 아니다

# 단말노드에서 시작하지 않게끔
for i, start in enumerate(tree):
    if len(start) > 1:
        dfs(i)
        break
# 모두 단말노드인 경우
if n==2:
    print(1)
else:
    print(len(early))

1. 배운점

   • 그래프, 트리 문제에서 단방향/양방향 확인 잘 해야겠다.
   • 양방향 그래프에서는 무한루프에 빠지지 않게끔 visited 확인해 줘야 한다
   • 트리, 그래프 문제는 꼭 그려봐야 풀 수 있다.
   • 반례 미리 예상해서 처리하는 연습 하자 11번이나 시도했다..ㅠㅠ