[BFS] 백준 이분 그래프 1707번 with Python3 ★

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

1707번: 이분 그래프

문제

정답 풀이

### bfs
import collections
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

for _ in range(int(input())):
    V, E = map(int, input().split())
    graph = [[] for i in range(V+1)] # 빈 그래프 생성
    visited = [0] * (V+1) # 방문한 정점 체크

    for _ in range(E):
        a,b = map(int, input().split())
        graph[a].append(b) # 무방향 그래프
        graph[b].append(a) # 무방향 그래프


    q = collections.deque()
    group = 1
    bipatite = True
    for i in range(1, V+1):
        if visited[i] == 0: # 방문하지 않은 정점이면 bfs 수행
            q.append(i)
            visited[i] = group
            while q:
                v = q.popleft()
                for w in graph[v]:
                    if visited[w] == 0: # 방문하지 않은 정점이면 큐에 삽입
                        q.append(w)
                        visited[w] = -1 * visited[v] # 현재 노드와 다른 그룹 지정
                    elif visited[v] == visited[w]: # 이미 방문한 경우, 동일한 그룹에 속하면 False
                        bipatite = False

    print('YES' if bipatite else 'NO')

출처:https://deep-learning-study.tistory.com/581

 

해석

 

 

 

내 풀이 -실패-

import sys
from collections import deque
input = sys.stdin.readline

# bfs 함수


def bfs_first(start):
    que = deque([start])
    visited[start] = 1

    while que:
        vv = que.popleft()

        for i in graph[vv]:
            if visited[i] == 0:

                que.append(i)
                visited[i] = 1


# def bfs_second(start):
#     que = deque([start])
#     visited2[start] = 1

#     while que:
#         vv = que.popleft()

#         for i in graph[vv]:
#             if visited[i] == 1:
#                 return False
#             if visited2[i] == 0:
#                 que.append(i)
#                 visited2[i] = 1
#     return True


# 입력
testcase = int(input())

for _ in range(testcase):
    vertex, lines = map(int, input().split())

    # 그래프 만들기
    graph = []
    for _ in range(vertex+1):
        graph.append([])

    for _ in range(lines):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    # 이분 그래프인지 검증
    check = 0
    for i in range(1, vertex+1):  # 각 vertex 마다
        if len(graph[i]) == 2:  # 간선이 두개라면
            # 함수 실행 전 초기화
            visited = [0] * (vertex + 1)

            # i 와 연결된 노드 두개
            first, second = map(int, graph[i])

            # print(f'1:{graph}')
            # i 와 1st 2nd 연결 끊기
            graph[i].remove(second)
            graph[i].remove(first)
            graph[second].remove(i)
            graph[first].remove(i)
            # print(f'2:{graph}')

            # 1st를 시작으로 bfs 탐색
            bfs_first(first)

            # 2nd가 방문되엇으면 이분 그래프가 아님.
            if visited[second] == 0:
                print('YES')
                check += 1
                break

            # 다시 연결 복원
            # print(f'3:{graph}')
            graph[i].append(second)
            graph[i].append(first)
            graph[first].append(i)
            graph[second].append(i)
            # print(f'4:{graph}')

    if check == 0:
        print('NO')

해설

알고리즘 로직을 구상할때 실수가 있었다. 이분 그래프라길래 이분 트리를 생각하고 있었고, 그럴 경우 간선이 두개만 연결된 노드를 기준으로 자르면 된다고 생각했다. 하지만 그렇지 않았다. 이 부분을 수정하려고 했으나 연결점을 자르고 붙히고 하는 작업이 간선이 여러개가 되면 너무 복잡하고 비효율적이게 된다.