알고리즘 스터디 첫번째 문제

<문제>

• 링크: 백준2533-사회망 서비스

<문제 풀이>

• 그래프 + dfs + 동적 계획법 이용

• vertex[n][1] : n이 어댑터일때 n과 자식을 포함한 어댑터의 총 수
• vertex[n][0] : n이 어댑터가 아닐때 n과 자식을 포함한 어댑터의 수
  ※ 그림에서 "숫자)" 는 dfs를 이용해서 호출되는 재귀 순서이다.

1)

• vertex[5][1] = 1 : 노드 '5'가 어댑터일때 자식을 포함한 총 어댑터 수
• vertex[5][0] =0 : 노드 '5'가 어댑터가 아닐때 자식을 포함한 총 어댑터 수

2)

• vertex[6][1] = 1
• vertex[6][1] = 0

3)

• vertex[2][1] : "자식노드(5)가 어댑터가 아닌 경우" + "자식 노드(6)이 어댑터가 아닌 경우" + "자기 자신이 어댑터 = vertex[5][0]+vertex[6][0]+1 = 1
• vertex[2][1] : "자식 노드(5)가 어댑터인 경우" + "자식 노드(6)이 어댑터인 경우" = vertex[5][1]+vertex[6][1] = 2

4)

• vertex[3][1] = 1
• vertex[3][1] = 0

5)

• vertex[7][1] = 1
• vertex[7][1] = 0

6)

• vertex[8][1] = 1
• vertex[8][1] = 0

7)

• vertex[4][1] = vertex[7][0]+vertex[8][0]+1 = 1
• vertex[6][1] = vertex[7][1]+vertex[8][1] = 2

8)

• vertex[1][1] = vertex[2][0]+vertex[3][0]+vertex[4][0]+1 = 5
• vertex[1][0] = vertex[2][1]+vertex[3][1]+vertex[4][1] = 3

» root 노드(1)에 도달하였고 root노드가 어댑터인 경우(vertex[1][1])와 어댑터가 아닌 경우(vertex[1][0])의 값을 비교하여 최소 값을 구한다. = "3"

<코드 구현>