이분 그래프
출처 | 이분 그래프 [백준 1707]
문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
제한
- 2 ≤ K ≤ 5
- 1 ≤ V ≤ 20,000
- 1 ≤ E ≤ 200,000
풀이 [BFS]
from sys import stdin
from collections import deque
def bfs(graph, start, visited):
dq = deque()
dq.append(start)
visited[start] = 1
while dq:
k = dq.popleft()
for i in graph[k]:
# 방문한 적 없는 노드는 서로 다른 그룹에 속하게 한다.
if visited[i] == 0:
visited[i] = visited[k] * (-1)
dq.append(i)
# 인접한 노드가 다른 그룹이면 넘어가고,
elif visited[i] == visited[k] * (-1):
continue
# 서로 같은 그룹이라면 NO를 출력한다.
elif visited[i] == visited[k]:
return "NO"
# 서로 떨어져있는 노드는 deque이 비었을 때 다시 확인한다.
# 즉, 모든 노드는 한번씩 탐색해야한다.
if not dq:
for i in range(len(visited)):
if visited[i] == 0:
dq.append(i)
visited[i] = 1
break
return "YES"
t = int(input())
for _ in range(t):
v, e = map(int, stdin.readline().split())
graph = [[] for _ in range(v+1)]
for _ in range(e):
a, b = map(int, stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
for i in range(1, v + 1):
graph[i].sort()
visited = [0] * (v+1)
visited[0] = 111
print(bfs(graph, 1, visited))정리
모든 노드를 탐색하는 작업을 재귀로 해결하려고 했을 때,
RecursionError라는 에러가 발생했다. RecursionError는 재귀와 관련된 에러이고, 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때이다.
이를 해결하기 위해
import sys
sys.setrecursionlimit(10**7) 재귀의 깊이 한계를 늘려보았지만 해결되지 않아 다른 방법을 생각했다.
출처
알고리즘 분류
기억창고👩🌾