728x90 그래프 탐색2 이분 그래프 (Bipartite Graph) 정리 이분 그래프(Bipartite Graph) 란? 이분 그래프(Bipartite Graph)는 그래프의 정점을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 의미한다고 합니다. 제가 풀이한 백준 1707번 이분 그래프 문제에서는 설명하고 있어 무슨 말인가 싶어 구글링을 통해 찾아본 결과 이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠했을 때 모든 정점을 두 가지의 색으로 칠할 수 있는 그래프이다! 이러한 성질로 인해서 같은 그룹의 정점끼리는 간선으로 연결되지 않고, 간선은 서로 다른 그룹에 대한 정점만을 연결하는 특징을 갖습니다. 참고로 간선 없이 하나의 정점으로 존재하는 그래프 또한 이분 그래프(Bipartite graph)라고 할 수 있습니다! 이분 그래프.. 2022. 9. 17. BOJ - 13460번 구슬 탈출 2, BFS 방식으로 풀이 (C++) 1. 문제 소개 이번에는 BFS 관련해서 풀이할 문제를 찾아보다가 적당히 어려울 것 같은 느낌 같아서 13460번 문제를 풀이했던 과정을 정리해 보려고 합니다. https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 아무리 어려워도 그래프 탐색인데, 라고 생각했는데 골드 1 난이도가 괜히 책정된 게 아닌 느낌으로 풀이하는데 굉장히 까다로웠습니다. 제 풀이 과정을 정리하기에 앞서 문제 설명을 간략하게 해.. 2022. 8. 25. 이전 1 다음 728x90
