[Python] 백준 2533번 - 사회망 서비스(SNS) 재귀 없이 짜기

인터넷에 돌아다니는 코드들은 전부 재귀로 돼 있어서 조금 색다르게

스택을 이용해 리프노드부터 탐색하는 코드를 올려본다.

스택을 이용하기 때문에 기본적으로 dfs방식이나 차이점은 리프노드인지 체크하여 최적화를 진행해야한다는 점이다.

리프노드부터 탐색하는 이유는 서브트리의 최적값을 갱신해 나가는 방식이기 때문이다.

이 부분을 보통 재귀로 계속 내려가다가 막다른 곳에 이를 때 최적화가 되도록 하는데 반복문으로 보이게 짜보았다.

방문하면서 연결된 길이 모두 방문한 길이어서 막다른 길이면 잎 노드로 판정하도록 변수를 하나 추가해줬다.

이렇게 막다른 길이라면 연결된 모든 길에 대해 최적화를 진행하는 방식이다.

최적화가 끝난 노드는 한 덩어리로 뭉쳐진다고 생각할 수 있다.

이때 연결된 모든 길을 체크하더라도 최적화 여부에 -1을 체크하여 부모 노드는 영향을 받지 않게 된다.

 

N = int(input())
adj_array = [[] for _ in range(N)]
for child in range(N-1):
  u, v = map(int, input().split())
  adj_array[u-1].append(v-1)
  adj_array[v-1].append(u-1)
# 방문은 0, 미방문은 1, 최적화 완료는 -1
visit = [1]*N
stack = [0]
d = [[0, 1]for _ in [0]*N]
while stack:
  node = stack[-1]
  # 잎 노드인지 확인
  isleaf = 1
  if visit[node] == 1:
    visit[node] = 0
    for child in adj_array[node]:
      if visit[child]:
        stack.append(child)
        isleaf = 0
  if isleaf:
    node = stack.pop()
    visit[node] = -1 # 최적화가 진행됐다고 표시한다.
    for child in adj_array[node]:
      # 최적화가 진행된 노드에 대해서만 수행한다.
      if visit[child] == -1:
        d[node][0] += d[child][1]
        d[node][1] += min(d[child][0], d[child][1])
print(min(d[0]))