4/12 Coding Test

✅ 문제 풀이 - BOJ (그래프 탐색)

🎈 1707 이분 그래프

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하는 문제
입출력은 다음과 같다.

• 입력 : 첫 줄에 테케 수 k, 각 테케 별 첫 줄에 그래프 정점 수 v, 간선 수 e가 주어지고 각 정점은 1~v까지 차례대로 번호가 붙어 있다. 이어 둘째 줄부터 e줄에 걸쳐 인접한 간선 정보가 주어지고 각 줄에 u, v가 주어진다.
• 출력 : k 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 출력하는 문제

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

def bfs(start):
    queue = deque([start])
    visited[start] = 1
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                queue.append(i)
                visited[i] = -1 * visited[x]
            elif visited[i] == visited[x]:
                return False
    return True

k = int(input())
for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    visited = [0] * (v+1)
    for _ in range(e):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    for i in range(1, v+1):
        if not visited[i]:
            answer = bfs(i)
            if not answer:
                break
    if answer:
        print('YES')
    else:
        print('NO')

< 풀이 과정 >
문제를 읽은 이후, 주어진 입력값들을 그래프로 처리해 union-find 알고리즘을 사용하려 했지만, 집합을 분리하는 경우의 수로 인해 메모리 초과가 발생할 것 같다는 생각이 들었다.

이후 DFS, BFS를 이용하여 방문한 기준을 -1과 1로 분리해야겠다는 사고를 한 이후, 그대로 구현하였다
과정은 다음과 같다.

• bfs 탐색으로 start인자로 시작해 vistied[start]를 1로 처리하고 덱에 start를 넣어 준다.
• 큐가 비기 전까지 반복하며 주어진 그래프의 인접 노드에 한해 방문하지 않은 곳에 한해 다른 그룹으로 처리해주기 위해 -1로 처리해준다.
• 이때 인접 노드 역시 기존 방문했던 그룹과 일치하면 이분 그래프가 아니므로 False를 리턴한다.
• 입력값들을 모두 처리한 이후, for문으로 노드에 한해 bfs탐색을 진행한 결과를 answer로 저장하고, 결과가 False면 break를 걸어 중단하여 시간 복잡도를 줄여준다.