potato's devlog

👉 문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 🧑🏻‍💻 문제 풀이 이분그래프 이면 1, 이분그래프가 아니면 -1를 flag에 저장해주었다. 정점은 각각 1과 -1로 구별해주었다. 만약 인접한 정점이 둘다 1이거나, 둘다 -1이라면 이건 이분그래프가 아닌거다! 이 값들은 visited 에 넣어주었다. 아래 코드는 main으로 돌아가는 부분이다. 차례대로 설명을 작성해보자면 처음 입력받는 K 만큼 result가 출력되어야 하므로 모..

🙋🏻‍♀️ 이분그래프 위 사진처럼 그래프가 '두개의 색'으로 표현되는 것을 이분그래프라고 한다. 빨간정점과 검은정점 두 그룹으로 나뉘었는데, 같은 그룹끼리는 인접하지 않아야한다. 즉, 그래프의 모든 정점이 두 그룹으로 나뉘어지고 서로 다른 그룹의 정점만이 간선으로 연결된 그래프를 말한다. 👻 이분그래프의 특징 이분 그래프인지 확인하기 위해서는 BFS와 DFS 탐색 방법을 이용할 수 있다. DFS와 BFS를 통해서 그래프를 탐색하게 되면, 같은 depth에 있는 정점은 같은 색을 갖게 되는 것이다. 연결 요소의 개수를 구하는 방법과 유사하다. 모든 정점을 방문해서 검사하기 때문에 시간복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다. 🧑🏻‍💻 이분그래프인지 확인해보는 방법 ⚠️ 주의사항: 서로 인접한 정..