728x90
🔗 문제링크 🔗
1953번: 팀배분
첫줄에는 청팀의 사람의 수를 출력하고, 그리고 둘째 줄에는 청팀에 속한 사람들을 오름차순으로 나열한다. 그리고 셋째 줄과 넷째 줄은 위와 같은 방법으로 백팀에 속한 인원의 수, 백팀에 속
www.acmicpc.net
🌟 생각 흐름 🌟
우선 문제를 풀기 위해서 싫어하는 사람들과의 표기를 그래프를 통해서 진행했다
그래프를 그린 후 한 노드에서 시작한 경우 현재 노드와 다음노드만 다른 팀이면 가능하다고 생각했다
그리고 그 다음노드에서의 다음노드가 서로 다른 팀이면 가능하다는 식으로 dfs로 구현하였다
그래서 한 노드에서 시작한후 현재 깊이가 짝수이면 청팀, 홀수 이면 백팀에 넣도록 코드를 구현하였다
예를 들어 1,2가 서로를 싫어하고 2,3이 서로를 싫어하는 경우
↔️ : 서로 싫어하는 경우 포기
1️⃣ ↔️ 2️⃣ ↔️ 3️⃣ 와 같이 표기할 수 있고
1에서 시작한 경우 아래와 같다.
1️⃣ : 청팀(깊이 0)
2️⃣ : 백팀(깊이 1)
3️⃣ : 청팀(깊이 2)
🍳 코드 🍳
728x90
'알고리즘' 카테고리의 다른 글
| [백준 Java]15711_환상의 짝궁_수학, 소수 (0) | 2023.02.25 |
|---|---|
| [백준 Java]1459_걷기_그리디 (0) | 2023.02.23 |
| 위상정렬 Topology Sort, 백준 1766 문제집(Java) (0) | 2023.02.22 |
| [백준 Java] 1238 파티 (다익스트라, 데이크스트라) (0) | 2023.02.21 |
| [백준 Java] 11054 가장 긴 바이토닉 부분수열 (0) | 2023.02.21 |
댓글