[알고리즘] 1707 이분그래프

1707 이분그래프

👌 문제 이해

이분 그래프란?

• 그래프의 정점의 집합을 둘로 분할하여 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 이분그래프라고 한다.
  

💡 문제 해결

알고리즘 : DFS
이유 :

생각해 봐야할것
1. 현재 탐색하는 노드와 인접한 노드를 어떻게 차이를 둘것인지?
-> 현재 탐색하는 노드에는 1값을, 인접한 노드에는 -1 값을 넣어서 차이를 둠

2. 노드가 연결되어 있지 않고 떨어져 있을 경우에는 어떻게 dfs를 돌 것인지?
   -> 각 노드별로 for문을 돌면서 dfs를 수행해줌, 이때 dfs는 이분 그래프 true,false를 확인할 수 있음

3. 각 노드의 값을 visited에 저장할 것
   -> visited에 False가 아닌 0값으로 넣어 줄 것

💻 코드

from sys import stdin as s
from collections import deque
import sys
sys.setrecursionlimit(10**6)

s=open("input.txt","rt")

n=int(s.readline())

def dfs(start,group):
    visited[start] =group #현재 노드의 그룹 저장
    
    #인접 노드 탐색
    for v in graph[start]:
        if visited[v]==0:
            result = dfs(v,-group) #-group : 현재 노드의 그룹과 다른 값 전달
            if not result:
                return False        
        else:
            if visited[v] == group:
                return False
    print(visited)
    return True


for _ in range(n):
    v,e = map(int,s.readline().split())
    graph = [[] for _ in range(v+1)]
    visited = [0] * (v+1)
    for _ in range(e):
        a,b = map(int,s.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    print(graph)
    for i in range(1, v+1):
        if visited[i] ==0: #각각 떨어져 있는 노드에 대해서도 이분그래프 인지 판별해줘야 하기 때문에 for문 돌림
            result = (dfs(i,1))
            if not result:
                break
        
    if result:
        print("YES")
    else:
        print("NO")

각각 떨어져 있는 노드에 대해서도 이분 그래프인지 판별해줘야 하기 때문에 각 노드별로 for문을 돌려서 dfs를 수행해준다.

🙄 잘못 생각 했던 점

visited 리스트에서 인접한 노드별로 값이 달라야 한다고 생각했는데, 다시보니까 노드들이 순차적으로 인접한 경우가 아닐 수도 있으므로 visited 리스트의 인접한 값이 다를 필요는 없다!
ex) visited =[0,1,-1,1,-1]-> 이분그래프...? -> 이분그래프가 아닐 수 있다!