[백준] 1707번 이분 그래프 _ Python

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

1707번: 이분 그래프

 

 

---

 

1. Preview

시간 복잡도: O(V+E)

 

공간 복잡도: O(V or E)

 

참고 : https://ji-gwang.tistory.com/293

 

유형: dfs, bfs

 

 

---

 

2. 초기 접근 방법

이분 그래프

: 인접한 정점끼리 서로 다른색으로 칠해서 모든 정점을 2가지 색으로만 칠할 수 있는 그래프

 

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

 

 

2개의 집합을 두고, 인접 노드를 번갈아 저장하는 이상한 방식으로 문제를 접근해 관련 내용 정리는 생략하였다;;

 

 

---

 

3. 생각

1) dfs

dfs 탐색을 진행하면서 인접 노드 색깔을 계속 바꿔준다.

이 때 인접 노드와 색깔이 같으면 False를 반환한다.

def dfs(start, idx):
    for k in graph[start]:
        # 인접 노드는 다른 "표식"
        if not visited[k]:
            visited[k] = -idx
            judge = dfs(k, -idx)

            # dfs 탐색 중에 인접 노드와 같은 "표식"이 있다면
            if not judge:
                return False

        # 인접 노드와 같은 "표식"이라면
        if visited[k] == visited[start]:
            return False

    return True

 

 

2) bfs

마찬가지로 bfs 탐색을 진행하면서 인접 노드 색깔을 계속 바꿔준다.

이 때 인접 노드와 색깔이 같으면 False를 반환한다.

def bfs(start):
    q = deque()
    q.append((start, 1))
    visited[start] = 1

    while q:
        node, idx = q.popleft()

        for k in graph[node]:
            # 인접 노드는 다른 "표식"
            if not visited[k]:
                visited[k] = -idx 
                q.append((k, -idx))

            # 인접 노드와 같은 "표식"이라면
            if visited[k] == visited[node]:
                return False

    return True

 

 

---

 

4. 코드

 

import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def dfs(start, idx):
    for k in graph[start]:
        # 인접 노드는 다른 "표식"
        if not visited[k]:
            visited[k] = -idx
            judge = dfs(k, -idx)

            # dfs 탐색 중에 인접 노드와 같은 "표식"이 있다면
            if not judge:
                return False

        # 인접 노드와 같은 "표식"이라면
        if visited[k] == visited[start]:
            return False

    return True


def bfs(start):
    q = deque()
    q.append((start, 1))
    visited[start] = 1

    while q:
        node, idx = q.popleft()

        for k in graph[node]:
            if not visited[k]:
                visited[k] = -idx # 인접 노드는 다른 "표식"
                q.append((k, -idx))

            # 인접 노드와 같은 "표식"이라면
            if visited[k] == visited[node]:
                return False

    return True


T = int(input())
for _ in range(T):
    V, E = map(int, input().split())

    graph = [[] for _ in range(V+1)]
    visited = [0 for _ in range(V+1)]

    for _ in range(E):
        s, e = map(int, input().split())
        graph[s].append(e) # 양방향 연결
        graph[e].append(s)

    for i in range(1, V):
        if not visited[i]:
            result = dfs(i, 1)
            if not result:
                break

    if result:
        print("YES")
    else:
        print("NO")