[BOJ] 1707번 이분 그래프 / 사용언어 : 파이썬(python)

※ 문제링크

1707번: 이분 그래프

※ 관련개념

[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog

해당 문제는 BFS로 해결할 수 있는 문제였다. 해결을 위해서는 우선 이분 그래프의 개념에 대해서 먼저 이해해야 했고, 해당 개념을 이해하기 위해 구글링을 하던 중 이해하기 쉽게 정리해준 글이 있어 해당 글을 참조한 후 코드를 작성하였다. 서로 연결되어 있는 정점들이 모두 다른 값을 가져야 이분 그래프가 될 수 있다는 것이 핵심이었고, 입력값을 바탕으로 딕셔너리를  활용하여 그래프를 구현한 후, BFS로 모두 점검하는 방식으로 문제를 해결하였다. 자세한 풀이와 코드는 아래와 같다.

1. 입력받은 값들과 딕셔너리를 바탕으로 그래프를 구현한다.

2. 간선들로 서로 연결된 정점들을 점검한 결과를 비교할 리스트를 만들고, 해당 리스트를 점검할 BFS함수를 작성한다.

3. 서로 연결된 정점들의 값이 동일하면 NO를 출력하고, 모든 경우를 점검하고도 이상이 없으면 YES를 출력한다.

+ 이분 그래프는 모든 정점이 연결되어 있지 않을 수 있으며, 이 경우 모든 그래프들이 이분 그래프여야 한다.(핵심)

+ 시간 및 메모리 단축을 위해 sys함수를 사용하였으며, 해당 함수 사용시에는 개행문자에 유의하도록 하자.

 

from collections import deque
import sys

# input = sys.stdin.readline
K = int(input())
for i in range(K):
    V, E = map(int, input().split()) # V: 정점의 개수 / E: 간선의 개수
    graph = dict()
    for _ in range(E):
        key, value = map(int, input().split())
        if key not in graph:
            graph[key] = [value]
        else:
            graph[key].append(value)
        if value not in graph:
            graph[value] = [key]
        else:
            graph[value].append(key)

    check = [0 for i in range(1, V+1)]

    def bfs(num):
        if check[num-1] == 0:
            check[num-1] = -1
            queue = deque()
            queue.extend(graph[num])
            cnt = 0
            while queue:
                if cnt % 2 == 0:
                    chp = -1
                    ch = 1
                else:
                    chp = 1
                    ch = -1
                for _ in range(len(queue)):
                    number = queue.popleft() 
                    if chp == check[number-1]:
                        return 0
                    elif check[number-1] == 0:
                        check[number-1] = ch
                        queue.extend(graph[number])
                    else:
                        pass
                cnt += 1
        return 1

    cp = -1
    for key, value in graph.items():
        cp = bfs(key)
        if cp == 0:
            ans = 'NO'
            break
    if cp == 1:
        ans = 'YES'
    if i == K-1:
        sys.stdout.write(f'{ans}')
    else:
        sys.stdout.write(f'{ans}\n')

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.