[Baekjoon, Python] 1707번 : 이분 그래프

도입

백준 단계별 풀기 DFS와 BFS 열 번째 문제이다.

백준 1707번 문제, 입력, 출력

---

백준 1707번 입출력 예제 1

---

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

---

이분그래프

위키백과 "이분그래프"

---

풀이

1. 쉽게 말해서 이분그래프란, 인접한 정점끼리 서로 다른 색으로 칠(빨,파)해서 모든 정점을 두가지 색으로 칠할 수 있는 그래프라고 보면 된다. 나는 mat_visit에서 1을 빨강, -1를 파랑으로 가정한다. 한 꼭짓점을 방문해서 연결된 다른 꼭짓점들의 visit 정보를 수정한다.

 

2. BFS로 푼다. 입출력 예제 1, 2를 구현한 BFS에 돌려서 본 결과 이다. 아래는, 초기의 mat_table과 완성된 mat_visit 변수의 결과 값이다. 

입출력 예제 1 2

---

 

코드

from sys import stdin
from collections import deque

def bfs(var_vtx):
    mat_visit[var_vtx] = 1    
    queue = deque()
    queue.append(var_vtx)
    while queue:
        vtx = queue.popleft()
        for i in mat_table[vtx]:
            if mat_visit[i] == 0:
                mat_visit[i] = -mat_visit[vtx]
                queue.append(i)
            else:
                if mat_visit[i] == mat_visit[vtx]:
                    return False
    return True

var_T = int(stdin.readline())

for _ in range(var_T):
    var_V,var_E = map(int, stdin.readline().split())
    bool_isBi = True
    mat_table = [[] for i in range(var_V+1)]
    mat_visit = [0 for i in range(var_V+1)]
    for _ in range(var_E):
        var_a,var_b = map(int, stdin.readline().split())
        mat_table[var_a].append(var_b)
        mat_table[var_b].append(var_a)
    for i in range(1,var_V+1):
        if mat_visit[i] == 0:
            if not bfs(i):
                bool_isBi = False
                break
    print("YES"if bool_isBi else "NO")

---

마무리

BFS에서 1, -1 로 설정해서 바꿔주는 BFS 로직이 생각보다 어려웠다. 바로 떠올리지 못한 점이 아쉽다.