반응형 graph1 [백준/C++] 이분 그래프 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 정점들의 집합을 두 개로 분류했을 때, 집합 내에 속한 정점들이 서로 인접하지 않게 할 수 있는지 판단하는 문제다. 어떻게 하면 문제를 풀 수 있을지 한번 그림으로 생각해보자 먼저 위의 왼쪽 그림의 경우를 살펴보자 하나의 정점이 속할 집합이 정해지면, 인접한 정점은 다른 집합에 속해야 한다. 그러므로 이를 이용해 하나의 정점이 0번 집합에 속했다면, 인접한 정점은 전부 1번 집합에 넣는다. 마찬가지로 하나의 정점이 1번 집합에 속했다면, 인접한 정점은 전부 0번 집합에 넣으면 된다. 이렇게 정점들의 집합을 두개로 나눠서 채워 넣으면 한 집합에 속해있는 정점들은 서로 인접하지 않도록 만들 수 있다. 그런.. 2024. 4. 14. 이전 1 다음 반응형
