[BOJ] 이분그래프 1707 ★

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

 

1. 문제 이해 및 해결과정

- 이분그래프의 개념이 문제만 보고 제대로 이해되지 않았다. - 이분 그래프는 인접한 정점끼리 서로 다른색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프이다. - 즉, 그룹은 두그룹으로 나누어진다.  1. 정점에 1~n까지 차례로 방문하고 색칠한다. (1과 -1로 칠했음) 2. 방문하지않았다면 check==0 ,이전의 정점과 다른색을 색칠한다. 3. 방문했었는데 새로운 곳이 내 색깔과 같다면 이분그래프가 아니다.

- BFS로 풀 시, 주의할 점 

 DFS에서는 깊이순으로 color / -color 로 색깔을 칠할 수 있지만

 BFS에서는 레벨별로 색깔을 칠하는 것이다. 그러므로 현재 칠해진 색깔과 비교하는 코드 에서 주의해야한다. 

 

 

2. 풀이방법

 1. [PYTHON] DFS, BFS

#이분 그래프
#https://www.acmicpc.net/problem/1707
import sys
from collections import deque
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
def DFS(v,color):
    global flag
    check[v]=color

    for i in adj[v]:
        if check[i]==color: #칠하려는 색깔로 이미 칠해져있을 경우, 이분그래프가 아님
            flag=0
            return
        if check[i]==0: #아직 안칠해져있으면
            check[i]=-color
            DFS(i,-color)

def BFS(v,color):
    global flag
    Q=deque()
    Q.append(v)
    check[v]=color
    while Q:
        v=Q.popleft()
        for i in adj[v]:
            if check[i]==check[v]:
                flag=0
                return
            elif check[i]==0:
                check[i]=-check[v]
                Q.append(i)



if __name__=="__main__":
    t=int(input())
    while t>0 :
        t-=1
        v,e=map(int,input().split())
        adj=[[] for _ in range(v+1)]
        check=[0]*(v+1)
        for _ in range(e):
            a,b=map(int,input().split())
            adj[a].append(b)
            adj[b].append(a)
        color=1
        flag=1
        for i in range(1,v+1):
            if check[i]==0: #방문했던 곳 다시 방문하면 안됨
                #DFS(i,color)
                BFS(i,color)
            if flag==0:
                break
        if flag==0:
            print("NO")
        else:
            print("YES")

 

 

3. 오답원인

 

4. 알게된 점