[ 문제 ]

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

[ 알고리즘 유형 ]

그래프 이론
그래프 탐색
너비 우선 탐색

[ 정답 코드 ]

BFS로 다시 문제풀이

from collections import deque
import sys
input = lambda: sys.stdin.readline()

def bfs(i, c): # 정점, 색상
    q = deque([i])
    visited[i] = True
    color[i] = c
    while q:
        i = q.popleft()
        for j in arr[i]:
            if not visited[j]:
                visited[j] = True
                q.append(j)
                color[j] = 3- color[i]
            else:
                if color[i] == color[j]:
                    return False
    return True

if __name__ == '__main__':
    k = int(input())
    for _ in range(k): # 테스트 케이스 
        v,e = map(int, input().split())
        color = [0] * (v+1)
        arr = [[] for _ in range(v+1)]
        for _ in range(e):
            a,b = map(int, input().split())
            arr[a].append(b)
            arr[b].append(a)
        
        answer = True
        visited = [False] * (v+1)
        for i in range(1, v+1):
            if not visited[i]:
                if not bfs(i, 1): # return False이면 종료
                    answer = False
                    break
        print('YES' if answer else 'NO')

[ 풀이 방법 ]

이분 그래프란 ?
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할

이분 그래프를 체크하기 위해 color 라는 리스트를 사용하여 색상으로 구분했다.

만약, 각 집합에 속한 정점끼리 색상이 같으면 이분 그래프가 아니다.

[ 풀이과정 이슈 ]

1. DFS로 풀었더니 메모리 초과가 발생하여 실패했다

from collections import deque
import sys
input = lambda: sys.stdin.readline()
sys.setrecursionlimit(10**6)

def dfs(i, c): # 정점, 색상
    color[i] = c
    for j in arr[i]:
        if color[j] == 0:
            if not dfs(j, 3-c):
                return False
        elif color[i] == color[j]:
            return False
    return True

if __name__ == '__main__':
    k = int(input())
    for _ in range(k): # 테스트 케이스 
        v,e = map(int, input().split())
        color = [0] * (v)
        arr = [[] for _ in range(v)]
        for _ in range(e):
            a,b = map(int, input().split())
            arr[a-1].append(b-1)
            arr[b-1].append(a-1)
        
        answer = True
        for i in range(0, v):
            if color[i] == 0:
                if not dfs(i, 1):
                    answer = False
        print('YES' if answer else 'NO')

2. BFS로 바꾸는 과정에서
   으아...

색상을 바꾸는 과정에서

color[j] = 3- color[i]
라고 작성해야하는데

color[j] = 3- c
로 작성해서... 처음 넘어온 변수 c로 색상 초기화해서 코드가 정상적으로 안돌아갔다...

DFS에서 BFS로 바꾸는데 생각보다 오래 걸렸다...
BFS 제대로 이해하지 못했다는 거겠지,,
문제를 더 열심히 풀어봐야겠다.