bipartite graph3 [자바] 백준 12893 - 적의 적 (java) 목차 문제 : boj12893 필요 알고리즘 이분 그래프, 그래프 탐색(BFS, DFS 등) 이분 그래프가 만들어지는지 파악할수만 있으면 풀 수 있다. 일반적으로 이분 그래프 판정을 위해 DFS나 BFS를 사용한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 생각과정은 다음과 같다. 1. 적의 적은 친구라고 계속해서 연결해나갈 때, 결국 어느 누구의 관점에서 보든 서로 연관이 있는(간선이 연결되어진) N명이 정확히 적과 .. 2023. 6. 18. 이분 그래프 (bipartite graph) 그래프의 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 이분 그래프(bipartite graph)라고 한다. 즉, 정점을 어떠한 방법으로든 두 개의 집합으로 나눴을 때 각 집합의 정점끼리 간선이 존재하지 않게 나눌 수만 있다면 이분 그래프이다. 예를들어 위 이미지에서 1,2,3은 이분 그래프이고 4는 이분 그래프가 아니다(4번의 경우 동일한 집합끼리 간선이 연결되어 있다. 이와 같이 홀수 길이의 사이클이 있다면 이분 그래프가 될 수 없다.). 또 3과 같이 서로 연결된 부분이 없더라도 어쨌든 이분 그래프의 정의를 위반시키지 않으므로 이분 그래프이다. 이분 그래프 판별방법은 다음과 같다. 1. 모든 정점에 대해 각 정점에서 dfs 혹은 bfs를 진.. 2022. 3. 23. 백준 1707 자바 - 이분 그래프 (BOJ 1707 JAVA) 문제 : boj1707 '그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.' 무슨말이냐면, 정점을 두개의 그룹으로 나눴을 때, 해당 그룹끼리는 간선이 없도록 나눌 수 있으면 이분 그래프라는 얘기이다. 아래의 그림을 보면 바로 이해가 될 것이다. 1,2,3은 이분 그래프를 그려봤다. 4는 이분 그래프가 아닌 경우이다. 즉, 어떻게든 2 종류의 정점으로 나눌 때 간선 연결된 것 끼리 같은 종류만 아니면 된다 (4번의 경우 노란 정점 둘이 간선이 연결되었으므로 이분 그래프가 아니다. 그리고 다른 방식으로 2종류로 나눠도 모두 마찬가지로 이분 그래프가 될 수 없다.). 또 .. 2022. 3. 22. 이전 1 다음
