티스토리 뷰
https://www.acmicpc.net/problem/1765
1765번: 닭싸움 팀 정하기
1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다.
www.acmicpc.net
그냥 이름이 재밌어 보여서 풀어보았는데 그래프 문제였습니다. 앞서 푼 문제를 dfs로 풀어서 이번에는 bfs로 풀었습니다.
닭싸움 할 때 팀을 알아야 하는 문제입니다. 최대 팀의 개수를 구하면 됩니다.
친구의 친구도 친구이고, 원수의 원수도 친구입니다.
그리고 팀은 모두 친구로 구성됩니다.
그러므로 원래 친구였던 그래프는 그대로 두고, 원수였던 그래프만 한 단계 건너 탐색하면 됩니다.
그렇게 탐색이 완료된 그래프에서 bfs로 계속 친구들을 탐색하여 탐색이 마무리되면 한 팀이 구성된 것입니다.
코드는 다음과 같습니다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1135 뉴스전하기 C++ (0) | 2022.02.22 |
|---|---|
| 백준 1328 고층빌딩 C++ (0) | 2022.02.10 |
| 백준 16562 친구비 c++ (0) | 2022.02.07 |
| 백준 11402 이항계수 4 C++ (0) | 2022.01.15 |
| 백준 2150 Strongly Connected Component C++ (0) | 2022.01.09 |
댓글