[Python/Baekjoon] 1707. 이분 그래프

💬 문제

문제 난이도: 백준 골드 4

문제 링크: https://www.acmicpc.net/problem/1707

❗️접근 방법

1. 이분 그래프란?
   그래프의 인접한 노드에 다른 색을 칠하려고 할 때, 단 2가지의 색만으로도 칠할 수 있는 그래프.
   -> 이분 그래프에서는 노드들을 두 그룹으로 나눌 때 같은 그룹에 있는 노드끼리는 인접하지 않아야 한다.
2. dfs를 활용해서 인접한 노드간에 색을 비교한다.
3. 비연결 리스트 또한 이분 그래프가 될 수 있기 때문에 for문을 돌며 모든 노드에 대한 색을 비교한다.

✅ 정답 코드

# 이분 그래프
import sys
from collections import defaultdict
input = sys.stdin.readline
print = sys.stdout.write
sys.setrecursionlimit(10 ** 9)

def dfs(start, color):
    global flag # 인접한 두 정점이 같은 색인지 # False: 같은 색이다(== 이분 그래프 아니다)
    if colors[start] == 0:
        colors[start] = color # 방문한 적이 없다면 color를 저장해주기
        for next in nodes[start]:
            if colors[next] != 0: # 방문한 적이 있다면(== color를 지정해 준 적이 있다면) color가 같은지
                if colors[next] == colors[start]:
                    flag = False
                    return 
            else: # 방문한 적이 없다면 해당 노드에 대해서 dfs 호출
                dfs(next, color*-1)

N = int(input())
for _ in range(N):
    V, E = map(int, input().split(' '))
    nodes = defaultdict(list)
    colors = [0 for _ in range(V+1)] # 이분 그래프가 되기 위해서는 2가지 색만으로도 인접한 노드들이 서로 다른 색이 되도록 칠할 수 있어야 한다.
    # 내 코드에선 초기의 모든 색은 0이고 1 또는 -1이라는 2가지 색으로 칠할 것
    # colors가 visited의 역할도 함께
    flag = True
    for _ in range(E):
        start, end = map(int, input().split(' '))
        nodes[start].append(end)
        nodes[end].append(start)
    for key in nodes: 
        dfs(key, 1)
    if flag:
        print('YES\n')
    else:
        print('NO\n')

✍️ 새롭게 배운 부분

• 비연결 리스트여도 이분 그래프일 수 있으므로, 모든 노드에 대한 dfs를 실행해주기 위한 for문이 필요하다.
• colors라는 리스트를 통해 색 비교뿐만 아니라 방문한 적이 있는지(visited)도 한번에 확인할 수 있다.