-
boj 1953 팀배분Problem_Solving 2018. 10. 25. 16:37
boj 1953 팀배분
문제 설명
학생을 청팀과 백팀으로 두팀으로 나누는데 각각의 학생은 싫어하는 학생이 있다.
각 팀에는 서로 싫어 하는 학생이 존재 하면 안된다.
문제 풀이
1 step
그래프를 생성할 때 싫어 하는 사람끼리 간선으로 연결 한다.
2 step
BFS로 탐색하면서 부모랑 다른 팀에 배정 시킨다.
3. step
각 학생을 순회하면서 2 step에서 구한 팀을 이용해 팀을 나누어 출력한다.
소스 코드
결과
사용 알고리즘GOC++BFS(List를 이용한 queue) 3212kb/4ms (input에서 string으로 받음) 1992kb/0ms 참고로 GO를 이용할 때 queue라이브러리가 존재하지만 List로 구현 하였습니다.
두개에 대한 차이는 차후 포스팅 할 예정입니다.^^
'Problem_Solving' 카테고리의 다른 글
Codeforce #515 Binary Numbers AND Sum (0) 2018.10.28 BOJ 16236 아기상어 (0) 2018.10.27 BOJ 2479 계단오르기 (0) 2018.10.25 boj11505 구간 곱구하기 (0) 2018.10.25 BOJ13911 집구하기 (0) 2018.10.25 댓글