[알고리즘] 백준1707 이분그래프 - 파이썬

드디어 BFS와 DFS 단계별 풀어보기 마지막 문제인 이분그래프 입니다. 마지막 문제를 가볍게 풀고 싶었지만 문제를 이해하는 것부터 막혔습니다.. 풀이도 어떻게 풀어야할지 몰라 결국 답을 찾아봤습니다.

 

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

1707번: 이분 그래프

 

 

풀이코드

from collections import deque
from sys import stdin

def bfs(start):
    visit[start] = 1 # 시작점은 1로 시작
    queue = deque()
    queue.append(start)
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if visit[i] == 0:
                visit[i] = -visit[x] # 방문된적이 없고 연결시 부호를 바꿔 넣어준다.
                queue.append(i)
            else:
                if visit[i] == visit[x]: # 방문된적이 있고 부호가 같다면 이분그래프가 아니다. False 리턴
                    return False
    return True


k = int(stdin.readline())
for _ in range(k):
    v, e = map(int, stdin.readline().split())
    isTrue = True
    graph = [[] for _ in range(v+1)] # 정점과 간선 정보를 가지고 그래프를 생성
    visit = [0 for _ in range(v+1)] # 이분그래프를 판별하기 위한 그래프
    for _ in range(e):
        a ,b = map(int,stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    for y in range(1, v+1):
        if visit[y] == 0: # 방문한 적이 없다면
            if not bfs(y):
                isTrue = False # 이분그래프가 아니라면
                break
    print("YES"if isTrue else "NO")

 

문제풀이

코드를 봐도 한번에 이해가 가지 않았습니다. 이럴땐 손으로 직접 그리면서 디버깅?하면서 이해하려고 노력했습니다. 또 주석에 설명을 달았습니다.

 

코드는 아래 블로그에서 참고하였습니다!

https://pacific-ocean.tistory.com/349

[백준] 1707번(python 파이썬)