https://www.acmicpc.net/problem/1765
1765번: 닭싸움 팀 정하기
1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다.
www.acmicpc.net
유니온 파인드로 접근했다.
풀이
원수를 담는 배열 enemy 2차원 배열을 생성하여 원수 관계가 들어오면 양방향으로 추가.
친구 관계가 입력되면 유니온을 통해 컴포넌트를 합친다.
모든 입력이 들어오고 나면 enemy 배열을 탐색하면서 원수의 원수를 찾아 서로 연결해 주면 된다.
남아있는 컴포넌트의 개수를 출력하면 정답이다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [20530] 양분 (0) | 2023.11.04 |
|---|---|
| [15559] 내 선물을 받아줘 (0) | 2023.10.31 |
| [23324] 어려운 모든 정점 쌍 최단 거리 (0) | 2023.10.25 |
| [23743] 방탈출 (0) | 2023.10.01 |
| [1833] 고속도로 설계하기 (0) | 2023.09.30 |