그래프 이론1 [C/C++] 백준 #1707 이분 그래프(그래프 이론) 이번 문제는 그래프가 주어졌을 때, 정점들을 두개의 그룹을 나누었을 때, 인접한 정점들이 같은 그룹에 없도록 만들 수 있다면 이분 그래프가 됩니다. 이 문제를 풀기 위해서는 1) 현재 그룹에 참여하지 않은 임의의 정점을 고른다. 2) 해당 정점을 그룹 1에 넣는다. 그런 후 해당 정점을 큐에 넣는다. 3) 큐에서 정점을 하나 가져온다. 큐가 비어 있다면 1)번으로 돌아간다. 3) 해당 정점과 인접한 정점들 중에 해당 정점과 같은 그룹에 속해 있으면 이분그래프를 만들 수 없다. 그렇지 않고 다른 그룹에 이미 들어 있다면, 해당 정점은 무시한다. 그룹에 속해 있지 않은 정점이라면 다른 그룹에 넣고, 큐에 넣는다. 4) 3)번으로 돌아간다. 알고리즘 자체는 쉬운데, 제가 작성한 소스는 현재 그룹에 참여하지 않.. 2022. 10. 1. 이전 1 다음
