문제 바로가기
문제:
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력:
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.
출력:
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
풀이:
이분 그래프 처음 접해본 그래프다. 알아보니 두 그룹으로 나눴을때 한 그룹안에 있는 숫자들은 서로 연결되어 있지 않다.
문제에 있는 입력값으로 들면
이런느낌. 쉽게 말하면 연결된 두 숫자가 속한 집합이 달라야 한다.
DFS, BFS 사용이 가능하다.
1. DFS
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(10**6)
t = int(input())
def dfs(node):
global result
# 다음 노드 탐색
for next_node in graph[node]:
# 다음 노드 색칠 안 되어 있으면
if visited[next_node] == -1 :
# 지금 노드가 1이면 다음 노드는 2이다, 반대도 동일
if visited[node] == 1:
visited[next_node] = 2
elif visited[node] == 2:
visited[next_node] = 1
# 그 다음 노드 색칠하러 출발
dfs(next_node)
# 다음 노드 이미 방문을 했음
else:
#다른 노드가 이미 방문했고, 지금 내가 방문 했는데 색깔이 같으면 안됨
if visited[node] == visited[next_node]:
result = False
return
for _ in range(t):
v, e = map(int,input().split()) # 정점, 간선
graph = [[] for _ in range(v+1)]
# 집합 여부 저장 할 visited
visited = [-1] * (v+1)
for _ in range(e):
a, b = map(int,sys.stdin.readline().split())
# 양방향 그래프
graph[a].append(b)
graph[b].append(a)
# 이분 그래프 가능여부
result = True
# 모든 노드 탐색
for i in range(1, v+1):
if visited[i] == -1: # 아직 방문 안 했으면
visited[i] = 1 # 1 이라는 색으로 색칠
dfs(i) # 연관 된 다음 노드 칠하러 출발
# 이분 그래프가 아니면 돌아옴
if result == False:
break
if result == False:
print("NO")
# 이분 그래프라면
else:
print("YES")
2. BFS
[백준] 1707: 이분 그래프 python 구현 / BFS, Bipartite Graph, 반례 집합
문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력
hye-z.tistory.com
BFS는 이분 코드를 참고하면 될것 같다.
댓글