백준 1707번 이분 그래프 파이썬 풀이

백준 1707번 이분 그래프 파이썬 풀이

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

---

이분그래프란?

위키백과

모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프

 

즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는(<=> 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프라고 함.

(청팀 백팀 같은 느낌??)

 

 

 

 

정답코드

#이분 그래프
import sys
from collections import deque
K = int(input())

for i in range(K):
    V,E = map(int, sys.stdin.readline().rstrip().split())
    graph = [[] for _ in range(V+1)] #빈 그래프 생성
    visited = [0] * (V+1)   #방문한 정점 체크
    
    #그래프 값 넣기
    for i in range(E):
        x,y = map(int,sys.stdin.readline().rstrip().split())
        graph[x].append(y) #무방향 그래프
        graph[y].append(x) #무방향 그래프

    q = deque()
    group = 1
    bipatite = True
    for i in range(1,V+1):
        if visited[i] == 0: #방문하지 않은 정점이면 BFS 수행
            q.append(i)
            #= vs == 실수 체크
            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[w] == visited[v]:
                        bipatite = False
    print("YES" if bipatite else "NO")

 

 

풀이과정

기존의 BFS와 풀이가 매우 유사하니, 차이점을 위주로 풀이과정을 서술한다.

 

1.for i in range(1,V+1) 의 for문을 보듯이, 기존의 BFS와 달리 모든 점을 체크한다.

-> 이분 그래프의 정의 때문

 

 

2.만약 인접한 경우 그래프의 정의에 의해 다른 팀에 속해야 하므로 -1 * visitied[v] 로 구분해주었다.

만약 기존에 같은팀으로 배정되었던 두 정점이 연결되어있는 것으로 밝혀지면 이분 그래프가 아니므로 

elif 조건을 아래와 같이 해주었다.

while q:
                v = q.popleft()
                for w in graph[v]:
                    if visited[w] == 0: #방문하지 않은 정점이면 큐에 삽입 
                        q.append(w)
                        visited[w] = -1 * visited[v]
                    elif visited[w] == visited[v]:
                        bipatite = False

 

 

배운점 && 공부방향

 

실수유형

1. = vs == 값 넣어줄 때 실수하지 말것