이 문제를 혼자서 풀었을 때에는 그냥 DFS 알고리즘으로만 풀어도 되는 것인가 생각했었습니다. 하지만 잘 풀리지 않아서 다른 블로그들을 참고해보니 트리에 DP를 적용시키는 문제라고 하더군요.. 여하튼 트리 형태에서 DP를 어떤 식으로 해야 하는지 본 문제를 풀면서 정리해보겠습니다.
2533번: 사회망 서비스(SNS)
페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망
www.acmicpc.net
문제 설명)
친구 관계 그래프에서 얼리어답터가 아닌 인원의 인접한 모든 친구가 얼리어답터면 아이디어를 받아들일 수 있다고 가정할 때에 모든 인원이 아이디어를 받아들이기 위해서 필요한 가장 적은 얼리어답터 수를 구하는 문제입니다.
여기서 중요한 점은 이 그래프가 트리라는 점입니다. 이는 본 문제의 내용에서 대놓고 명시해줍니다.
일반적인 그래프에서 이 문제를 푸는 것이 매우 어렵다는 것이 알려져 있기 때문에, 친구 관계 그래프가 트리인 경우, 즉 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우만 고려한다.
그렇다면, 트리와 그래프의 차이가 무엇일까요?
- 그래프
- 어떠한 지점인 노드와 이를 잇는 간선으로 구성된 자료구조
- 연결된 객체들 간의 관계를 알 수 있다
- 순환 혹은 비순환 구조이다
- 부모 - 자식 관계가 존재하지 않는다
- 트리
- 그래프의 일종이다
- 비순환 관계이다 (사이클이 없다)
- 부모 - 자식 관계가 존재하고 이에 따라 Root노드(최상위 노드)가 존재한다
문제 안에서 나온 참고 그림들이 각각 그래프와 트리의 예이므로 이를 참고하면 이해가 더 잘 될 겁니다.
참고 1) 그래프 형태의 친구 관계 그래프
참고 2) 트리 형태의 친구 관계 그래프
문제에서는 트리 형태의 관계만 고려한다고 했으므로 우리는 그래프에서의 사이클이 나타나는 경우는 고려하지 않아도 되겠습니다.
그리고 다시 문제로 돌아가서 보면 이와 같은 말이 있는데, 이 문장이 상당히 중요합니다.
어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adaptor)라고 하는데, 사회망 서비스에 속한 사람들은 얼리 아답터이거나 얼리 아답터가 아니다. 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다.
저는 여기에서 다음과 같은 조건을 확인할 수 있었습니다.
- 자신이 얼리어답터가 아닐 경우 : 자신의 모든 친구가 얼리어답터여야 한다.
- 자신이 얼리어답터인 경우 : 친구 각각이 얼리어답터일 수도, 아닐 수도 있다.
그럼 앞서 참고 2의 관계를 가지고 이 두 조건에 맞추어 문제를 풀어보도록 하겠습니다.
문제 풀이)
위의 트리에서 1번 노드를 앞서 조건에 따라 각각 몇 명의 얼리어답터가 필요한 지 확인해보면 다음과 같습니다.
- 노드 1이 얼리어답터인 경우 : 노드 2, 노드 3, 노드 4가 각각 얼리어답터인지 아닌지 알 수가 없다.
- 노드 1이 일단 얼리어답터이므로 1 + min(노드 2가 얼리어답터인 경우 필요한 얼리어답터 수, 노드 2가 얼리어답터가 아닌 경우) + min(노드 3) + min(노드 4)가 최소의 얼리어답터 수가 된다.
- 노드 1이 얼리어답터가 아닌 경우 : 노드 2, 노드 3, 노드 4는 모두 얼리어답터이다.
- 노드 2가 얼리어답터였을 때 하위 노드에 필요한 최소의 얼리어답터 수 + 노드 3 (이하 생략) + 노드 4 (이하 생략)가 최소의 수가 될 것이다.
노드 1의 경우를 알기 위해서 저절로 자식 노드들의 경우의 수를 고려할 수밖에 없게 되었습니다. 즉, DP(다이내믹 프로그래밍)을 통해 풀 수 있다는 뜻이 됩니다. 그리고 트리에서 이것을 하기 위해서는 가장 깊은 노드부터 최적의 수를 구해서 올라가야 하므로, DFS를 합쳐서 풀 수 있습니다.
그렇다면 최하단부터 각 노드의 두 가지 경우의 수(해당 노드가 얼리어답터인지 아닌지)에 따라 각각의 DP값을 알아보도록 하겠습니다.
( DP [각 노드의 인덱스][ if 얼리어답터 : 1, if 일반인 : 0 ], 부모 노드가 얼리어답터인지는 해당 부모 노드의 DP를 구할 때에 고려하므로 각각의 노드의 DP를 구할 때에는 자식 노드만 고려해서 수를 구합니다.)
DP [2][1] = 1 + 0 (DP [5]의 최솟값) + 0 (DP [6]의 최솟값)
DP [2][0] = 2 (자식 노드(친구들)가 모두 얼리어답터이므로 DP [5][1] + DP [6][1])
DP [5][1] = 1 + 0 / DP [5][0] = 0
DP [6][1] = 1 + 0 / DP [6][0] = 0
DP [1][1] = 1 + 1 + 0 + 1 = 3 (1 + 각 노드의 DP 최솟값의 합)
DP [1][0] = 1 + 1 + 1 = 3 (모든 자식 노드가 얼리어답터인 경우의 합)
DP [2][1] = 1 / DP [2][0] = 2
DP [3][1] = 1 / DP [3][0] = 0
DP [4][1] = 1 / DP [4][0] = 2
그리하여, 최종적으로 DP [1][1]과 DP [1][0]의 값을 비교해서 더 작은 값을 구하면 문제의 답을 도출할 수 있습니다. 다만 이번 경우에는 2, 3, 4가 얼리어답터인 경우와 1, 2, 4가 얼리어답터인 경우 모두 다 최소의 얼리어답터 수 3을 만족시킬 수 있습니다.
'Algorithm > Computational Thinking' 카테고리의 다른 글
| BOJ 2516 (원숭이) - CT 풀이 (0) | 2022.05.19 |
|---|---|
| BOJ 21758 (꿀 따기) - CT 풀이 (0) | 2022.05.16 |
| BOJ 19940 (피자 오븐) - CT 풀이, 첫 게시글 (0) | 2022.05.16 |