[BOJ] 1707. 이분 그래프

Jimeaning·2023년 7월 4일

BFS 그래프

코딩테스트

목록 보기

106/143

Python3

문제

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

키워드

그래프 탐색
너비 우선 탐색
깊이 우선 탐색
이분 그래프

문제 풀이

문제 요구사항

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

이분 그래프에 대한 설명

변수 및 함수 설명

K: 테스트 케이스의 개수
V, E: 그래프의 정점의 개수 V, 간선의 개수 E
f, t: 각 줄에 인접한 두 정점의 번호

adjList: 무방향 그래프
visited: 방문 처리 리스트
flag: 이분 그래프인지 확인하는 변수

bfs(): bfs 탐색

풀이

(입력 및 선언)

테스트 케이스 개수 입력 받기
테스트 케이스만큼 반복
정점과 간선의 개수 입력 받기
두 정점의 번호를 리스트에 저장해 무방향 그래프로 만들기

정점의 개수만큼 반복
방문하지 않은 노드라면 bfs를 호출한다
만약 False가 반환되면 반복문을 종료한다

(bfs 함수)

방문하지 않은 노드를 매개변수로 받아 방문 처리를 하고 큐에 넣는다
큐에 원소가 없을 때까지 반복한다
큐의 첫 번째 원소를 curNum에 저장한다

그래프 내 정점의 개수만큼 반복한다
만약 방문하지 않은 노드라면, 큐에 추가하고 상위 노드와 다른 그룹으로 설정한다.

방문하지 않은 노드 : 0
빨간색 그룹 : 1
파란색 그룹 : -1

인접한 노드와 다른 그룹이어야 이분 그래프가 성립한다.
만약 인접한 노드가 서로 같은 그룹이라면 이분 그래프가 될 수 없으므로 바로 False를 반환하는 것이 시간 복잡도 줄이는 데 도움

만약 이미 방문한 노드이고, 같은 그룹이라면 이분 그래프가 아니므로 False를 반환한다.
모든 조건을 통과했다면 True를 반환한다

(최종 출력)

만약 bfs함수에서 True가 반환되면, 'YES'를 출력하고 그렇지 않으면 'NO' 반환

최종 코드

from collections import deque
import sys

k = int(sys.stdin.readline())

def bfs(start):
    visited[start] = 1
    bfsQueue = deque([start])
    while bfsQueue:
        curNum = bfsQueue.popleft()
        for element in adjList[curNum]:
            # 방문하지 않은 노드라면, 큐에 추가하고 상위 노드와 다른 그룹으로 편성
            if visited[element] == 0:
                bfsQueue.append(element)
                visited[element] = -visited[curNum]
            # 만약 이미 방문한 노드인데 같은 그룹이라면 False 리턴
            elif visited[element] == visited[curNum]:
                return False
    return True

for _ in range(k):
    v, e = map(int, sys.stdin.readline().split())

    adjList = [[] for _ in range(v+1)]
    visited = [0 for _ in range(v+1)]

    for _ in range(e):
        f, t = map(int, sys.stdin.readline().split())
        adjList[f].append(t)
        adjList[t].append(f)

    flag = True

    for i in range(1, v+1):
        # 방문하지 않았다면 bfs 호출
        if visited[i] == 0:
            # result = bfs(i)
            # if not result:
            if not bfs(i):
                flag = False
                break
    
    if flag:
        print('YES')
    else:
        print('NO')