최근 오픈소스 컨트리뷰톤과 연구 진행 때문에 알고리즘 풀 시간이 없었다. 그래도 감 잃으면 안되니 오늘 하나 풀고 작성해보고자 한다

문제 : https://www.acmicpc.net/problem/2533

문제

문제에서는 사이클이 없고 트리형태의 그래프로만 주어진다고 말하였다. 그리고 해당 그래프에서 얼리어답터의 최소개수를 구하라고 한다. 얼리어답터 개수를 구하는 방식은 현재 노드를 기준으로 현재 노드가 얼리어답터일 때와 아닐 때를 나눠 구하면 될거 같다. 자세한 풀이는 바로 다음에 설명하겠다

풀이

문제를 쪼개서 현재 노드오 그의 주변노드만을 고려해보자. 그렇다면 탐색할 때 두가지 경우만 탐색하면 된다.
1. 현재노드가 얼리어답터일때
주변 노드가 얼리어답터일수도 있고, 아닐수도 있다
2. 현재노드가 얼리어답터가 아닐때
주변노드들 모두 얼리어답터여야 한다.

위 경우를 토대로 쉽게 dfs내 if문을 작성할 수 있다. 또한 dp를 생성하여 최솟값만을 갱신하여 답을 도출하면 끝!!

여기서 시작노드는 무엇으로 잡아야되나?

시작노드는 아무거나 고르면 된다. 왜냐하면 전체탐색을 통해 개수를 구하는 것이기 때문에 어디서든 출발하여 탐색하면 되므로 필자는 1로 지정하였다.
질문을 보니 루트노드가 꼭 1이여야 하는 이유는? 물어보던데 위와 같은 이유이다.

code

import sys
sys.setrecursionlimit(10**7)

n = int(sys.stdin.readline())
dic = {i:[] for i in range(1,n+1)}
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().split())
    dic[a].append(b)
    dic[b].append(a)
    
dp = [[-1] * (n+1) for _ in range(2)]
visit = [False] * (n+1)

def dfs(start):
    global dp,visit
    visit[start]=True
    dp[0][start]=0
    dp[1][start]=1
    
    for _next in dic[start]:
        if not visit[_next]:
            dfs(_next)
            dp[1][start] += min(dp[0][_next], dp[1][_next])
            dp[0][start] += dp[1][_next]
    
    

dfs(1)
print(min(dp[0][1], dp[1][1]))

result

pypy3와 python3가 차이가 나는 것은 알았지만 이렇게까지 영향을 끼칠줄 몰랐다. 자세한건 구글링을 통해 조사해야겠지만 되도록이면 pypy3를 쓰고 메모리초과가 날 경우 python3을 쓰되 sys.stdin.readline()을 사용하여 입력을 받자
(pypy3는 메모리를 대략적으로 잡아서 메모리초과 위험이 있다고 한다)