[백준] 이분 그래프 (1707번) - Python / 알고리즘

✅문제 - 이분 그래프 (1707번)

---

 

✅필요 알고리즘 개념 - BFS

---

🔵 BFS 활용 방법

◼ 이 문제는 연결된 두 Node를 다른 색으로 색칠하는 것이 가능한지 물어보는 문제이다.

 

예를 들어 아래 처럼 인접한 두 노드를 서로 다른 색으로 칠할 수 있다면 이분 그래프로 나눌 수 있는 그래프이다.

 

하지만 아래의 경우 Node 5번을 보면 빨간 Node와 파란 Node와 모두 연결돼 있기 때문에 인접한 Node와 다른 색으로 칠할 수 없다. 그러므로 이분 그래프가 아니다.

이 아이디어를 활용하여 BFS를 구현하면 이분 그래프를 확인할 수 있다.

✅코드 설명 - BFS 구현 부분

---

def bfs(graphs,visited):
    queue = deque()
    # graphs 는 edge를 입력 받은 list이다
    # visited 는 방문하지 않은 경우 0 방문한 경우 1 or 2로 색을 구분한다.
    
    for i in range(1,len(graphs)):
        # for문을 통해 모든 node에 대해 확인한다.
        # 왜냐하면 BFS를 시작해서 que를 끝내더라도
        # 시작점과 아예 연결 되어 있지 않은 node가 있을 수 있기 때문이다.

        if visited[i] == 0:
            visited[i] = 1
            queue.append(i)
            # queue가 끝나도 아직 방문하지 않은 node 인 경우
            # 색을 1로 초기화 하고 que를 진행
            # 이때 선행한 que와 아예 접점이 없는 node이므로
            # 어떤 색으로 초기화 하던 상관이 없고
            # 이분 그래프인지 아닌지만 중요하다.
            
            while queue:
                node = queue.popleft()
                flag = visited[node]

                for v in graphs[node]:
                    if visited[v] == 0:
                        visited[v] = 3 - flag
                        queue.append(v)
                    elif visited[v] == flag:
                        # 인접한 node와 색이 같은 경우 False를 return하며 종료
                        return False
                    else:
                        continue
    return True

 

 

✅전체 코드 

---

import sys
from collections import deque

test_num = int(sys.stdin.readline().rstrip())

def bfs(graphs,visited):
    queue = deque()
    
    for i in range(1,len(graphs)):
        if visited[i] == 0:
            visited[i] = 1
            queue.append(i)
        
            while queue:
                node = queue.popleft()
                flag = visited[node]

                for v in graphs[node]:
                    if visited[v] == 0:
                        visited[v] = 3 - flag
                        queue.append(v)
                    elif visited[v] == flag:
                        return False
                    else:
                        continue
    return True

for _ in range(test_num):
    vertex,edge = map(int,sys.stdin.readline().rstrip().split())
    graphs = [ [] for _ in range(vertex+1)]
    visited = [ 0 for _ in range(vertex+1)]

    for _ in range(edge):
        start,end = map(int,sys.stdin.readline().rstrip().split())
        graphs[start].append(end)
        graphs[end].append(start)
    
    if bfs(graphs,visited):
        print("YES")
    else:
        print("NO")