99클럽 코테 스터디 9일차 TIL + 백준 1707 이분 그래프 (파이썬)

※ 1707 이분 그래프

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

문제 해결 TIP

문제를 먼저 이해해보자.

이분 그래프란 아래 그림과 같이, 이웃하는 정점끼리 가지는 색깔이 달라야 하는 것이다.

bfs로 구현하여 주변 정점들을 탐색하면서 색칠해주고, 만약 색깔이 다르다면 이분 그래프가 아니다라는 판단을 내릴 수 있다.

 

전체 코드

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

K = int(input())
for i in range(K):
    V, E = map(int,input().split())
    graph = [[] for _ in range(V+1)]
    color = [0]*(V+1)
    for j in range(E):
        u, v = map(int,input().split())
        graph[u].append(v)
        graph[v].append(u)
    flag = 1

    def bfs(start):
        global flag
        queue = deque()
        queue.append(start)
        color[start] = 1
        while queue:
            v = queue.popleft()
            for i in graph[v]:
                if color[i] == 0:
                    queue.append(i)
                    if color[v] == 1:
                        color[i] = 2
                    elif color[v] == 2:
                        color[i] = 1
                elif color[v] == color[i]:
                    flag = 0

    for k in range(1,V+1):
        if color[k] == 0:
            bfs(k)
    if flag:
        print("YES")
    else:
        print("NO")

---

• 비기너 문제 : 전주 듣고 노래 맞히기  https://www.acmicpc.net/problem/31562
• 미들러 문제 : DFS와 BFS https://www.acmicpc.net/problem/1260
• 챌린저 문제 : 비슷한 단어 https://www.acmicpc.net/problem/2179