(JAVA) 백준 2533번 : 사회망 서비스(SNS) -- [DP, DFS]

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

2533번: 사회망 서비스(SNS)

 

 

이 문제에서 가장 중요한 부분은 "트리" 구조 인 것 같습니다.

 

트리를 위해 클래스를 만들고, 이를 1차원 배열로 만든 Graph를 활용한다면, 기존 2차원배열(또는 ArrayList[] 배열) 을 활용한 Graph보다 훨씬 시간과 메모리를 줄일 수 있습니다.

물론, 2차원 int배열은 말할것도 없구요.

*** (Edge와 vertex 개수만큼만 만드는 것이 아닌 모든 경우의 수를 그래프로 그리는 것이기 때문에 상당히 비효율적 -> O(n^2))

 

 

문제의 핵심입니다.

1) 만약 영희가 얼리어답터가 아니면?

  -> 이웃한 철수, 순희는 얼리어답터여야 한다.

2) 만약 영희가 얼리어답터면?

  -> 이웃한 철수, 순희는 얼리어답터 일수도, 아닐수도 있다.

 

즉,

부모 노드가 얼리어답터가 아니면 자식 노드들은 전부 얼리어답터여야 하지만,

부모 노드가 얼리어답터이면 자식 노드들은 반드시 얼리어답터여야 하지 않아도 됩니다.

 

이를 DP와 DFS로 조합한다면,

 

 

가장 핵심인 트리

1)

노드 1은 자식 노드(이웃한 노드)인 2, 3, 4만 확인하면 됩니다.

노드 1은 얼리어답터일수도, 아닐수도 있으니 두 가지 경우가 존재하고, 이를 DP를 활용해 int[n][2] 인 2차원 배열로 나타낼 수 있습니다.

여기에 들어갈 수 있는 값은 자식노드인 2, 3, 4가 가질 수 있는 최소의 얼리어답터 개수를 더한 값입니다.

이를 파악하기 위해 DFS 재귀함수 호출을 통해 자식노드부터 탐색합니다.

(y 인덱스 : 노드 1 ~ n, x 인덱스 : 0 -> 노드 y가 얼리어답터가 아닌 경우, 1 -> 노드 y가 얼리어답터인경우)

 

 

 

2)

자식 노드인 2, 3, 4 노드의 자식 노드를 확인합니다.

노드 2는 노드 1과 마찬가지로 얼리어답터일수도, 아닐수도 있으니 자식 노드들이 가질 수 있는 최소의 얼리어답터 수를 파악해 전부 더한 결과를 가집니다.

 

 

만약, 2가 얼리어답터가 아닌 경우(dp[2][0]) -> 모든 자식들이 얼리어답터여야 함

dp[2][0] += dp[5][1] + dp[6][1]

 

만약, 2가 얼리어답터인 경우(dp[2][1]) -> 모든 자식들은 각각 얼리어답터일수도, 아닐수도 있음 -> 얼리어답터 개수가 최소인 값을 가져옴

dp[2][1] += Math.min(dp[5][0], dp[5][1]) + Math.min(dp[6][0], dp[6][1])

 

 

 

 

3)

이렇게 구한 자식의 dp값을 가지고 부모의 dp를 구할 수 있습니다.

쭉 거슬러 올라가다보면 초기 호출했던 루트 노드의 dp를 구할 수 있고, 가장 최소의 얼리어답터 개수 또한 얻을 수 있습니다.

 

 

 

DFS 알고리즘은 하단 소스코드를 참고하시면 됩니다.

 

감사합니다!

 

 

ArrayList 배열로 구한 소스코드

---

 

 

 

 

 

 

트리 클래스를 만든 소스코드

---