adfsfsf   1년 전

아주 간단하게 생각해서, 친구를 갖고 있는 사람 중 친구 수가 가장 적은 사람 A와 A의 친구 중 친구 수가 가장 적은 f를 쌍으로 만들어 주는 것을 반복했습니다.

이전에는 DFS를 써보기도 했으며, VSCode 기준으로 예제나 게시판의 케이스들은 전부 통과했습니다.

zenith82114   1년 전

10 16
3 4
1 8
3 10
1 4
6 7
1 7
8 9
2 9
6 10
4 8
5 10
4 5
3 9
2 5
7 8
2 8

현재 출력은 9, 정답은 10입니다.

adfsfsf   1년 전

이 문제가 그리디하게는 풀 수 없는 문제였나보군요...
너무 간단하게 생각했었네요.

adfsfsf   1년 전

그리디하게 푸는 문제는 맞는데, 노드 단위가 아니라 쌍 단위로 잡아야되었네요...

제가 최종적으로 푼 방법은 다음과 같습니다.

1. 각 상태에서, 아직 방문하지 않은 노드 중 간선 수가 가장 적은 노드를 골랐습니다. 이를 Mnode라 하겠습니다.
2. 그 노드와 연결된, 아직 쌍을 갖지 않은 노드들을 구합니다. 이를 Snodes라고 하겠습니다.
3. Snodes의 각 노드에 대해, Mnode와 연결되었다고 가정한 후 그 상태를 기준으로 다시 1번으로 돌아갑니다.
4. 만약 Snodes가 없다면 단순히 Mnode에 대해 방문 처리를 한 후 1번으로 돌아갑니다.
5. 모든 노드에 대해 방문하거나, 쌍을 만들어줬다면 최댓값을 갱신합니다.

만약 노드 단위로 그리디하게 가면 그래프의 중간에서 먼저 쌍이 생겨서 양끝의 노드들이 남는 경우가 생기는 것으로 보입니다.

그런데 DFS가 알고리즘 분류에 있는 건 이해가 잘 안 되네요...
DFS로 탐색 시 쌍 단위로 해보지 않아서 그런 것 같아요.

확실한 건, 이 문제는 순수 그리디로도 해결된다는 것입니다.

댓글을 작성하려면 로그인해야 합니다.