백준 1707 문제 분석 python

🐒 이분 그래프

https://www.acmicpc.net/problem/1707

✍ 나의 풀이

import sys
from collections import deque

input = sys.stdin.readline


K = int(input())

def bfs(start, group):
    q = deque()
    q.append(start)
    visited[start] = group
    while q:
        x = q.popleft()

        for i in graph[x]:
            if not visited[i]:
                q.append(i)
                visited[i] = -1 * visited[x]
            elif visited[i] == visited[x]:
                return False
    return True

for _ in range(K):
    V, E = map(int,input().split())

    graph = [[]for _ in range(V+1)]
    visited = [False] * (V+1)
    for _ in range(E):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    
    for i in range(1, V+1):
        if not visited[i]:
            result = bfs(i, 1)
            if not result:
                break
    
    print(visited)
    print('YES' if result else 'NO')

문제에서 말하는 이분 그래프를 이해하는데 실패하고 구글링했다.
참고한블로그

---

🧠 문제 이해

이분그래프는 서로다른 두개의 그룹이 있을때 그룹A에 속한 정점이 그룹A에 속한 정점과는 연결되지 않는 그래프이다.

그림에서 파란색정점 다음에 빨간색, 빨간색정점 다음에 파란색 정점이 연결되어있는 모습을 볼 수 있다.

---

def bfs(start, group):
    q = deque()
    q.append(start)
    visited[start] = group
    while q:
        x = q.popleft()

        for i in graph[x]:
            if not visited[i]:
                q.append(i)
                visited[i] = -1 * visited[x]
            elif visited[i] == visited[x]:
                return False
    return True

bfs함수는 정점과 1을 인자로 받아서 방문리스트에 1 또는 -1을 엇갈려 넣어 그룹을 구분한다.
연결된 정점을 확인하는데 현재 그룹과 정점의 그룹이 같다면 False를 반환하여 본 그래프가 이분그래프가 아님을 알 수 있게된다.

---

똑똑한 사람들이 많아요