[그래프]백준_1707_이분 그래프

• 알고리즘 유형 : 그래프, bfs, dfs, 이분 그래프
• 풀이 참고 : 여러 블로그 풀이들
• 문제 링크 : https://www.acmicpc.net/problem/1707

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다. 

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사 드리겠습니다. 

---

이분그래프의 간단 설명

1. 모든 인접한 노드를 서로 다른색으로 칠할 수 있어야 한다.

  - 처음 보고 당연히 무슨말인지 몰랐다. 

2. 쉽게 말해서

  - 인접한 노드끼리는 무조건 다른색으로 되어 있어야 한다. 

  - 연결되어 있는 노드가 같은색이다? 이분그래프 아님

 

---

풀이 요약

1. True and False로 색깔 여부 체크

2. 모든 노드가 연결되어 있지 않는 경우 고려

---

코드(python)

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

def bfs(start_node):
    visited[start_node] = 1 # 방문 노드 1
    queue.append(start_node)
    while queue:
        pop_x = queue.popleft()
        for i in arr[pop_x]:
            if visited[i] == 0: # 방문한 노드일때
                visited[i] = -visited[i] # 해당 노드를 -로 체크
                queue.append(i)
            else:
                if visited[i] == visited[pop_x]:
                    return False
    return True        

# 케이스 = k
k = int(input())
for i in range(k):
    v, e = map(int, input().split())
    arr = deque([[] for _ in range(v+1)])
    visited = [0] * (v+1)
    # [0, 0, 0] , [0, 0, 0, 0, 0]
    queue = deque([])
    for j in range(e):
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)

    # 노드를 색칠 할 변수
    part = True
    # 첫번째 arr은 1번 케이스, 두번째 arr은 2번 케이스 
    # [[], [3], [3], [1, 2]] , [[], [2], [1, 3, 4], [2, 4], [3, 2]]
    for j in range(1, v+1):
        if visited[j] == 0: # 방문하지 않은 노드 중
            if not bfs(j): # bfs를 탐색 했을때 False면 
                part = False
                break
    print("YES" if part else "NO")

---

배운 점, 배울 점

- 어렵다. 

- 그래프 탐색에 대한 코드 이해가 아직 부족 한 것 같다. 

- 함수에서 return 으로 값을 받아내는 쪽의 이해가 부족하다. 

- 다른 쉬운 문제들에서 함수를 최대한 활용하며 공부해야 겠다.