최대독립집합 썸네일형 리스트형 BOJ 3683 고양이와 개 https://www.acmicpc.net/problem/3683 고양이와 개가 나오는 티비쇼가 있고 사람들이 투표를 한다. 투표가 반영이 되면 시청자로 남고 반영이 안되면 시청을 그만둔다. 쇼 제작자는 시청자를 최대로 유지하고 싶다. 문제를 다른 시각으로 보기 사람들 (혹은 플레이어, 참여자) 사이에 의견이 있다. 두 사람 사이의 의견에 충돌이 있으면, 두 사람도 만족을 하는 결과는 없다. 최소한 둘 중 하나는 결과에 불만족 하게 된다. (둘 다 될 수도 있다.) 이 문제를 그래프로 모델링 하기 위해 사람을 그래프를 구성하는 정점으로 볼 수 있다. 두 사람 사이의 의견 충돌이 있으면, 두 사람 사이에 간선을 추가 해서 의견 충돌을 모델링 할 수 있다. 그럼 이 문제는 서로 의견이 대립되지 않는 사람의 .. 더보기 이전 1 다음