[ BOJ 1707 ] 이분그래프(Python)

문제

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

이분 그래프의 개념을 이해하는데에 시간이 조금 걸렸다.

이분그래프

인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.
즉, 서로 다른 그룹의 정점이 간선으로 연결되어 있고, 같은 그룹에 속한 정점끼리는 서로 인접하지 않는 그래프를 말한다.

문제 풀이

간선으로 연결된 정점은 서로 다른 그룹이다.
visited를 체크할 때 서로 다르게 체크해주면 된다.

1. 정점 간 연결된 간선을 입력 받아 양방향으로 연결해주었다.

2. bfs 함수의 매개변수로 들어온 정점 v에 1로 방문 체크 표시를 해주고, 정점을 queue에 넣어준다.
   ➣ visited[v] = 1

3. 정점 v와 연결된 모든 다른 정점 u에 대해서, 정점 u를 방문 안했으면 방문 체크를 해준다.
   3-1. visited[v]가 1인 경우, visited[u]는 -1로 방문 체크를 해준다.
   3-2. visited[v]가 -1인 경우, visited[u]는 1로 방문 체크를 해준다.
   3-3. 방문 체크를 해준 정점 u를 queue에 넣어준다.

4. 만약 정점 u는 방문했지만, 정점 v와 연결된 정점 u가 같은 그룹이면 NO를 출력한다.

5. 위에 해당되지 않으면 YES를 출력한다.

코드

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


T = int(input().rstrip())
for _ in range(T):
    v,e = map(int,input().rstrip().rsplit())
    graph = [[] for _ in range(v+1)]
    visited = [0] * (v+1)

    for _ in range(e):
        x,y = map(int,input().rstrip().rsplit())
        graph[x].append(y)
        graph[y].append(x)

    def bfs(v):
        queue = deque()
        queue.append(v)
        visited[v] = 1

        while(queue):
            v = queue.popleft()
            for u in graph[v]:
                #print(u,visited)

                #정점 u를 방문 안했을 때
                if not visited[u]:
                    #정점 v의 그룹이 '-1'일때, 연결된 정점인 u의 그룹은 '1'/ '1'일땐 '-1'로 번갈아가면서 설정해준다.
                    if visited[v] == 1:
                        visited[u] = -1
                    elif visited[v] == -1:
                        visited[u] = 1
                    queue.append(u)
                    
                #정점 u는 방문했지만, 정점 v와 연결된 정점 u가 같은 그룹이면 NO를 출력한다.
                elif visited[u] == visited[v]:
                    return 0
        return 1
        
    check = False
    for i in range(v):
        #방문하지 않은 노드만 bfs로 호출해서 들어가기
        if visited[i]==0:
            ans = bfs(i)
            if ans == 0 :
                check = True
                break

    if check == True:
        print("NO")
    else:
        print("YES")
    # print(dfs(1,0))