[파이썬python] 백준 1707번 - 이분 그래프

백준 1707번 이분 그래프 문제를 풀어보겠습니다. 

문제풀이는 물론, 이분 그래프에 대해서 알아보고

제가 문제를 어떻게 접근해나갔는지에 대한 과정이 담겨있으니 끝까지 집중해주세요!

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

1707번: 이분 그래프

문제요약) 

입력으로 주어진 그래프가 이분 그래프면 YES, 아니면 NO를 순서대로 출력한다.

 

문제에 나와있는 이분 그래프의 설명인데요.

여러분들은 이해가 되시나요? 저는 이해가 잘되지 않았어요.

그래서 이분 그래프를 검색해봤습니다. 

위 그림 처럼 인접한 정점끼리 서로 다른 색을 칠해서

모든 정점을 두 가지 색으로만 칠할 수 있는 그래프가 이분 그래프라고 하더라고요!

이제 다시 문제에 나와있는 이분 그래프 설명으로 돌아가보겠습니다.

그래프의 정점의 집합을 둘로 분할하여(두 가지 색으로 칠해진 정점: 빨간색 점 집합, 검정색 점 집합)
각 집합에 속한 정점끼리는 서로 인접하지 않도록 (빨간색 정점, 검정색 정점끼리는 서로 연결되어 있지 않습니다. 간선x)
분할 할 수 있을 때 그러한 그래프를 이분 그래프라 부른다.

그럼 이제 이분 그래프인지 아닌지 판단하는 아이디어에 대해서 이야기해보겠습니다. 

아래의 그림은 인접해있는 3번과 4번 정점이 인접해있어서 이분 그래프가 아닌 경우입니다.

저는 bfs를 통해 2번 정점이 3번, 4번정점과 연결되어있으므로,

큐에 3번, 4번을 넣을 때,

따로 3번, 4번이 연결되어있는지 확인하면 되지 않을까라는 접근을 했습니다. 

하지만 구현을 하다보니까 for문을 통해 각각 3번, 4번이 큐에 삽입이 되기 때문에

3번과 4번이 연결되어있는지 확인하는 코드를 어디에 넣으면 좋을지 잘 모르겠더라고요.

 

그리고 구글링을 했죠..ㅎㅎ

말로는 어려우니 코드로 이해해보도록 하겠습니다.

 

정답코드)

from collections import deque

def bfs(num):
    q = deque()
    q.append(num)
    visit[num] = 1
    while q:
        x = q.popleft()
        for i in board[x]:
            if visit[i] == 0:
                visit[i] = -visit[x]
                q.append(i)
            else:
                if visit[i] == visit[x]:
                    return False
    return True


num1 = int(input())
for i in range(num1):
    n,m = map(int, input().split())
    board = [[] for _ in range(n+1)]
    visit = [0] * (n + 1)
    flag = 1
    for _ in range(m):
        a,b = map(int,input().split())
        board[a].append(b)
        board[b].append(a)

    for i in range(1,n+1):
        if visit[i] == 0:
            if not bfs(i):
                flag = -1
                break
    print('YES' if flag == 1 else 'NO')

그리고 되도록 행렬보다는 인접리스트로 간선들을 입력받아야 시간이 줄어듭니다! (O(v^2) 와 O(v+e))

def bfs(num):
    q = deque()
    q.append(num)
    visit[num] = 1
    while q:
        x = q.popleft()
        for i in board[x]:
            if visit[i] == 0:
                visit[i] = -visit[x]
                q.append(i)
            else:
                if visit[i] == visit[x]:
                    return False
    return True

 

visit[i] == 0:   //방문한 적이 없으면  

visit[i] = -visit[x]  //visit배열에 부모의 visit배열 값의 음수를 저장합니다.

위에 예시에서는 3번과 4번이 같은 visit배열 값을 가지겠죠? (둘다 2번의 자식이니까)

이분 그래프는 인접한 정점이 다른 색깔로 칠해질 수 있는 그래프라고 했는데요!

이때 3번과 4번이 같은 색깔로 칠해지는 겁니다.

 

따라서 다음 popleft되는 3번 순서일 때 3번과 연결되어있는 정점은 2번과 4번인데,

visit[3]과 visit[4]가 같은 값을 가지므로(같은 색) else로 분기되어서 False로 return됩니다. 

 

import sys
sys.setrecursionlimit(10000)

def dfs(now,group):
    visit[now] = group
    for i in arr[now]:
        #안 가본 곳
        if visit[i] == 0:
            if not dfs(i,-group):
                return False
        #가봤는데 색깔이 같으면
        elif visit[i] == visit[now]:
            return False
    return True

num = int(input())
for _ in range(num):
    n,m = map(int,input().split())
    arr = [[] for _ in range(n+1)]
    visit = [0 for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,input().split())
        arr[a].append(b)
        arr[b].append(a)
    ans = True
    for i in range(1,n+1):
        if visit[i] == 0:
            ans = dfs(i,1)
            if not ans:
                break
    print("YES" if ans else "NO")

위의 코드는 dfs로 풀이한 코드입니다.

설명방식은 같습니다.