Coding - Algo/python
[백준] 1707번:이분 그래프 (python 파이썬)
jainn
2021. 2. 24. 13:44
728x90
문제
1707번: 이분 그래프
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수
www.acmicpc.net
풀이
처음엔 배열을 이용해 dfs를 사용하려 했는데, 메모리초과가 났다 ㅠㅠ
1과 2가 연결되어 있으면 arr[1][2] = arr[2][1] = 1 이런식으로 했더니 . . !
방법을 바꿔서 bfs로 deque를 사용하여 해결했다.
이분그래프란, 간단히 말하면 인접한 정점끼리 다른 색으로 칠할 수 있는 그래프이다.
이를 visited 배열을 통해 방문하지 않았으면 0으로, 방문하였으면 -1과 1로 구분해주었다.
소스코드
import sys
input = sys.stdin.readline
from collections import deque
def bfs(x):
visited[x]=1
q = deque()
q.append(x)
while q:
a = q.popleft()
for i in que[a]:
if visited[i]==0:
visited[i] = -visited[a]
q.append(i)
else:
if visited[i] == visited[a]:
return False
return True
k = int(input())
for i in range(k):
v, e = map(int, input().split())
que = [[] for i in range(v+1)]
visited = [0]*(v+1)
flg = 1
for j in range(e):
a, b = map(int, input().split())
que[a].append(b)
que[b].append(a)
for k in range(1, v+1):
if visited[k]==0:
if not bfs(k):
flg = -1
break
print('YES' if flg==1 else 'NO')
반응형