이분 그래프3

• 

  [백준/BOJ] 12893번: 적의 적 문제 https://www.acmicpc.net/problem/12893 12893번: 적의 적 첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다. www.acmicpc.net 해설 A와 B가 적대 관계고 B와 C가 적대 관계라면, A와 C는 우호 관계가 된다. 이 때, C와 D가 적대 관계라면, A와 C가 우호 관계이고, B와 D가 우호 관계가 된다. 결론은 두개의 팀으로 나눈다는 것이다. 즉, 이분 그래프가 성립이 되는지 안되는지를 구하는 것이다. 이분 그래프의 설명은 이 글을 참고하면 좋다. 코드 import j.. PS(Problem Solving)/BOJ 2022. 8. 17.

• 

  [백준/BOJ] 1707번: 이분 그래프 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 해설 처음 문제를 풀 때, 이분 그래프를 트리처럼 사이클이 없는 그래프라고 생각하였어서 계속해서 틀렸습니다가 떴다. 백준의 질문 검색을 통해 질문을 하였고, 금방 댓글이 달려 이분 그래프가 나의 생각과는 완전히 다르다는 것을 알고 이분 그래프에 대해 공부를 한 후 문제를 풀어보았다. 이분 그래프에 대한 설명은 이 글을 읽어보면 도움이 될 것이다. 이 문제에서 주의할 점은 특정 정점에서만 이분.. PS(Problem Solving)/BOJ 2022. 8. 16.

• 

  [알고리즘] 이분 그래프(Bipartite Graph) 이분 그래프란? 정점을 두 그룹으로 나눌 수 있으면서, 같은 그룹끼리는 간선으로 이어지지 않은 그래프이다. 트리가 아닌 그래프이므로, 사이클이 있어도 상관없으나, 같은 색상의 정점끼리 연결은 있어서는 안된다. 간선이 단 한도 없고 정점만 있는 상태도 이분 그래프이다. 여기에서 알 수 있듯이, 모든 정점이 꼭 연결되있어야 하는 것이 아니다. 이분 그래프 구현 이분 그래프는 DFS 또는 BFS를 사용하여 구현할 수 있다. 나는 BFS가 더 익숙하여 BFS를 사용할 것이다. 백준의 1707번 이분 그래프 문제를 예시로 들어보자. import java.util.* import kotlin.collections.ArrayList private lateinit var color: IntArray private la.. Algorithm 2022. 8. 16.