99클럽 코테 스터디 _ 9일차 TIL (이분 그래프, BFS)

 

< 문제 >

[백준] 1707. 이분 그래프 / 골드4

---

< 풀이 >

코드 변수 정의

• graph : 인접 리스트 그래프
• colors : 정점 색상 표시 배열
• results : 이분 그래프이면 YES, 아니면 NO

---

BFS
시간복잡도 : O(k * (V + E))

from collections import deque

# 이분 그래프인지 확인하는 함수
def is_bipartite_graph(V, E, edges):
    # 그래프 초기화
    graph = [[] for _ in range(V + 1)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # 색상 표시 배열 (0: 미방문, 1: 검정, -1: 흰색)
    colors = [0] * (V+1)

    # BFS를 통한 이분 그래프 판별
    def bfs(start):
        queue = deque([start])
        colors[start] = 1  # 시작 정점을 검정으로 칠함

        while queue:
            current = queue.popleft()
            for neighbor in graph[current]:
                if colors[neighbor] == 0:  # 방문하지 않은 경우
                    colors[neighbor] = -colors[current]  # 다른 색으로 칠함
                    queue.append(neighbor)
                elif colors[neighbor] == colors[current]:  # 같은 색이 인접함
                    return False
        return True

    # 모든 정점에서 BFS를 수행하여 이분 그래프 여부 확인
    for i in range(1, V + 1):
        if colors[i] == 0:  # 미방문 정점만 확인
            if not bfs(i):
                return False
    return True


def main():
    k = int(input())  # TC 수
    results = []

    for _ in range(k):
        V, E = map(int, input().split())
        edges = []
        for _ in range(E):
            u, v = map(int, input().split())
            edges.append((u, v))
        # 이분 그래프 여부 판별
        results.append("YES" if is_bipartite_graph(V, E, edges) else "NO")

    print(*results, sep='\n')

if __name__ == "__main__":
    main()

---

 

 

풀이 방식

1. 그래프 초기화
   • edges 내에 (u, v)로 있는 모든 edge를 기반으로 그래프를 인접 리스트 형태로 표현한다.
   • 그래프 구조
     • graph[i] : 정점 i에 연결된 인접 정점의 리스트를 저장
     • 예시 ) edge = (1, 2)   →   graph[1]에 2 추가 / graph[2]에 1 추가
2. 색상 배열
   • 인접한 정점이 다른 색상이어야 하므로, 색상을 표시하여 확인한다.
     • 0 : 미방문
     • 1 : 검정색
     • -1 : 흰색
3. BFS 탐색
   • 시작 위치
     • start 정점을 1로 표기한다.
   • 큐를 이용하여 탐색 반복
     • 현재 위치(current)의 모든 인접 정점(neighbor)을 확인한다.
   • 인접 정점 처리
     • 방문하지 않은 정점 (colors[neighbor] == 0)
       • 현재 정점의 반대 표시(현재가 1이면 반대 색인 -1 로 표기)하고 큐에 추가
     • 이미 방문한 정점
       • 색상이 현재 정점과 같으면 이분 그래프가 아니다.
   • 결과 반환
     • BFS 탐색 결과 == False (색상이 같은 정점이 인접한 경우)
       • return False
     • BFS 탐색 결과 == True (색상이 같은 정점이 인접한 경우가 없으면)
       • return True
4. 그래프의 모든 정점 탐색
   • 연결되지 않은 그래프도 처리하기 위해 모든 정점을 확인한다.
   • 방문하지 않은 정점(colors[i] == 0)만 BFS 탐색을 한다.
   • 연결된 모든 요소가 이분 그래프여야만 True를 반환한다.

 

---

< 회고 >

이분 그래프(Bipartite Graph)

인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프

• 그래프의 모든 정점을 두 그룹으로 나누고, 각 그룹에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프.

특징

• 이분 그래프인지 확인하는 방법 : BFS, DFS 탐색
• 이분 그래프는 BFS를 할 때, 동일한 레벨의 정점끼리 모두 같은 색을 갖는다.
• 연결 성분의 개수(Connected Component)를 구하는 방법과 유사
• 시간 복잡도 : O(V + E)   *모든 정점을 방문하며 간선을 검사

 

 

 

 

---

 

출처

이분 그래프 - url