백준 1953번 팀배분

문제 링크입니다: https://www.acmicpc.net/problem/1953

1953번: 팀배분

N이 최대 100이기 때문에 시간복잡도 O(N^3)으로도 풀 수 있는 BFS 알고리즘 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 각 사람이 팀 하기 싫어하는 사람들의 목록을 벡터(haters)를 통해 입력 받습니다.

2. 1번부터 N번 사람까지 순회하며 아직 팀을 꾸리지 않았으면 청팀에 배치를 합니다.

2.1 2번에서 청팀에 배치한 사람이 싫어하는 사람 중 아직 팀을 꾸리지 않은 사람들을 백팀에 배치를 합니다.

2.2 2번과 2.1 과정을 반복하며 사람들을 최대한 팀에 배치시킨 뒤 더 이상 팀을 배치할 사람이 없다면 다음 사람으로 넘어가 2번부터 2.2번 과정을 반복합니다.

3. 문제 조건에 팀에 속한 사람들을 오름차순으로 나열한다 라는 조건이 있으므로 2번 과정을 완료하고 각 팀을 오름차순 정렬 해줍니다.

4. 문제 조건에 단, 각 팀에는 최소 1명의 사람이 있어야 한다. 라는 조건이 있으므로 2번 과정을 완료했을 때 한 쪽 팀에 모든 사람들이 있다면 isOneSided 함수를 호출하여 팀에 속한 마지막 사람을 반대 팀에 배치하고 프로그램을 마칩니다.

5. 4번에 해당하지 않는다면 문제 조건에 맞춰 출력을 해주고 프로그램을 마칩니다.

 

개발환경:Visual Studio 2019

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~