hjhj97

[Codeforces 1176E] Cover it! 문제 설명 :undirected edge로 이루어진 그래프가 주어진다. 이 그래프에서 최대 floor(n/2)개의 node들을 선택하여 '선택된 node들과, 선택되지 않은 node간의 거리가 1'이 되기 위해서 어떻게 node를 선택해야 하는지 묻는 문제이다. 풀이 : 풀이는 매우 간단하다. 아무 노드에서부터 다른 노드들까지의 최단거리를 구한다(bfs나 dfs를 이용하면 된다). 그러면 그 거리가 짝수인 node들과 홀수인 node들로 그룹이 나눠질텐데 두 그룹 중에서 원소의 개수가 더 작은 그룹이 곧 정답이 되는 것이다.이것이 가능한 이유는 짝수 -> 홀수 -> 짝수 -> 홀수 .... 형태가 반드시 반복된다는 확신이 있기 때문이다. 현재의 노드가 ..