[백준] 1707 이분그래프 (Python 파이썬)

www.acmicpc.net/problem/1707

1707번: 이분 그래프

문제 설명

문제에서 말한 이분그래프란, 그래프 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 말한다.

즉, 그래프의 정점을 두가지 색으로 칠할 때, 인접한 정점끼리는 다른 색을 가지고 있는 그래프 인 것이다.

위 그림은 대표적인 이분그래프이다.

---

풀이 과정

visited[V]에 1, 2의 값을 줌으로써 정점의 색을 구분한다. ( 단, 아직 미방문 정점은 0 )

BFS를 수행하기 전에 인접행렬로 그래프를 만들어 준다.

그리고 탐색을 수행하면 되는데, 이 때 주의해야 할 점이 있다.

바로, 비연결 그래프에 대해서도 고려를 해야 한다는 점이다.

연결 그래프의 경우에는 시작점에서 BFS를 수행하면 모든 정점을 탐색할 수 있지만,

비연결 그래프의 경우에는 시작점과 연결되지 못한 정점은 아직 탐색을 수행하지 않기 때문이다.

그래서 아래 코드의 "for k in range(1, V + 1): " 를 통해 모든 정점에서 BFS를 한 번씩 수행하도록 하였다.

from collections import deque

k = int(input())


def bfs(graph, start):
    queue = deque()
    queue.append(start)
    if visited[start] == 0:
        visited[start] = 1  # 이분은 1, 2로 하고 아직 방문하지 않은곳은 0으로 표시
    while queue:
        v = queue.popleft()

        color = visited[v]
        for i in graph[v]:  # V정점과 연결된 모든 정점 확인
            if visited[i] == 0:  # 아직 한번도 방문하지 않음
                queue.append(i)  # 다음에 방문할 곳으로 지정
                if color == 1:  # 현재의 정점과 다른 색상으로 색칠
                    visited[i] = 2
                else:
                    visited[i] = 1
            elif visited[i] == 1:
                if color == 1:
                    print("NO")
                    return False
            elif visited[i] == 2:
                if color == 2:
                    print("NO")
                    return False
    return True


for i in range(k):
    flag = 0
    V, E = map(int, input().split())
    graph = [[] for _ in range(V + 1)]
    visited = [0] * (V + 1)
    for j in range(E):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    for k in range(1, V + 1): # 연결그래프일 경우에는 시작점에서 한번의 BFS를 수행하면 되지만 비연결그래프의 경우에는 모든 정점을 탐색해야 한다.
        if not bfs(graph, k):
            flag = 1
            break
    if flag == 0:
        print("YES")

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !