코드

from collections import deque

T = int(input())

for _ in range(T):
    # v : 정점의 개수
    # e : 간선의 개수
    v, e = map(int, input().split())

    # 정점의 개수 v+1만큼 그래프 생성
    graph = [[] for _ in range(v+1)]

     # 정점 방문 여부 체크할 리스트
    visited = [0] * (v+1)

    # 그래프 연결 상태를 입력 받음 => 무방향 그래프
    for _ in range(e):
        a, b = map(int, input().split())

        # 무방향 그래프
        graph[a].append(b)
        graph[b].append(a)

    # 이분 그래프인지 판별 => BFS, DFS 사용
    def bfs(graph, start):
        q = deque()
        q.append(start)

        # 이분 그래프는 그룹이 두 개로 나누어짐
        # 0 : 미방문
        # 1 : 그룹 1
        # 2 : 그룹 2
        if visited[start] == 0:

            # start노드에 방문하면 그룹 1에 포함
            visited[start] = 1

        while q:
            v = q.popleft()

            # 현재 방문한 간선의 그룹
            part = visited[v]

            # 현재 노드와 연결된 노드 체크
            for i in graph[v]:

                # 방문한 적 없으면
                if visited[i] == 0:
                    # 다음 탐색 노드로 설정
                    q.append(i)

                    # 현재의 정점과 다른 그룹으로 설정
                    # 1, 2는 내가 임의로 부여한 그룹 (2개니까 그냥 편의상 1, 2로 설정)
                    # 자신과 연결된 첫번째 노드는 다른 그룹이어야 하므로 다른 그룹으로 설정
                    if part == 1:
                        visited[i] = 2
                    else:
                        visited[i] = 1

                # 방문한 경우
                else:
                    
                    # 현재 방문한 노드의 간선과 같은 그룹이면
                    # 이분 그래프가 아님 => False 반환
                    if visited[i] == part:
                        return False

        # 같은 그룹이 아니면 True 반환
        return True

    # bfs가 False를 반환하는 경우를 체크하기 위한 변수
    check = True 
    
    # 연결 그래프는 시작점에서 BFS를 한 번만 수행해도 괜찮지만
    # 비연결 그래프는 모든 정점에 대하여 탐색을 수행해야 한다
    for i in range(1, v+1):
        
        # bfs의 결과가 False => 이분 그래프가 아님 => NO 출력
        if not bfs(graph, i):
            check = False
            print("NO")
            break

    # check가 끝까지 True인 경우 => 이분 그래프 => YES 출력
    if check:
        print("YES")

문제 해설

주어진 그래프가 이분 그래프인지 판별하는 로직을 만드는 문제.

이분 그래프 위키

BFS를 이용하여 주어진 그래프가 이분 그래프가 맞는지를 파악하면 된다.

기본적인 해결 로직은 아래와 같다.

  1. visited 리스트에 방문 여부 및 그룹을 0, 1, 2로 나누어 부여

  2. 방문한 노드와 인접한 노드가 같은 visited의 값을 가지고 있다면 이분 그래프가 되지 못하므로 False를 반환, 그렇지 않은 경우 True를 반환하는 함수를 작성

  3. 반환 값을 이용하여 False인 경우 NO 출력, True인 경우 YES 출력

DFS와 BFS는 정말 많이 사용되는 것 같다. 몇 번이고 반복하여 내 것으로 만들 수 있게 숙달해야겠다!!!

댓글남기기

참고