https://www.acmicpc.net/problem/1707
그래프의 노드에 2가지 색칠하는데 인접한 노드끼리 서로 다르게 색칠할 수 있는지 묻는 문제이다.
dfs로 돌면서 색칠하고, 만약 방문했다면 현재 노드와 방문하려고 했던 노드의 색이 같은지 다른지에 따라 결과가 나오게 했다.
from collections import defaultdict
def dfs(start, color, graph, visited, chk):
for next in graph[start]:
if visited[next] == -1:
visited[next] = abs(color-1)
chk = dfs(next, abs(color-1), graph, visited, chk)
visited[next] = -1
elif visited[next] == visited[start]:
chk = False
return chk
for _ in range(int(input())):
v, e = map(int, input().split())
graph = defaultdict(list)
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [-1 for _ in range(v+1)]
visited[1] = 0
print("YES" if dfs(1, 0, graph, visited, True) else "NO")
dfs로 했는데 시간초과가 났다.
from collections import defaultdict
for _ in range(int(input())):
v, e = map(int, input().split())
graph = defaultdict(list)
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [-1 for _ in range(v+1)]
visited[1] = 0
que = [(1, 0)]
idx = 0
chk = True
while idx < len(que):
if not chk:
break
now, color = que[idx]
idx += 1
for next in graph[now]:
if visited[next] == -1:
que.append((next, abs(color-1)))
visited[next] = abs(color-1)
elif visited[next] == visited[now]:
chk = False
break
print("YES" if chk else "NO")
BFS로 바꿔봤는데, 재귀도 안 쓴 코드인데도 시간초과가 발생했다. 왜지 도대체라고 생각했는데 연결되지 않은 그래프가 있는 경우를 고려하지도 못했고, input도 겁나 커서 그런 것 같았다.
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(start, color, graph, visited):
visited[start] = color
for next in graph[start]:
if visited[next] == -1:
if not dfs(next, 1 - color, graph, visited):
return False
elif visited[next] == color:
return False
return True
for _ in range(int(input())):
v, e = map(int, input().split())
graph = defaultdict(list)
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [-1 for _ in range(v+1)]
answer = True
for i in range(1, v+1):
if visited[i] == -1:
if not dfs(i, 0, graph, visited):
answer = False
print("YES" if answer else "NO")
초기화 절차를 조금 수정하고, visited를 참고해서 모든 점에 대해서 방문하지 않았다면 검사하도록 했다. 그리고 readline으로 입력 속도를 늘리고 recursion 제한을 풀어주었다.
from collections import defaultdict
import sys
input = sys.stdin.readline
for _ in range(int(input())):
v, e = map(int, input().split())
graph = defaultdict(list)
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [-1 for _ in range(v+1)]
chk = True
for i in range(1, v+1):
if visited[i] == -1 and chk:
visited[i] = 0
que = [(i, 0)]
idx = 0
while idx < len(que) and chk:
now, color = que[idx]
idx += 1
for next in graph[now]:
if visited[next] == -1:
que.append((next, abs(color-1)))
visited[next] = abs(color-1)
elif visited[next] == visited[now]:
chk = False
break
print("YES" if chk else "NO")
BFS에서는 readline으로 입려제한을 풀어주었다.
그리고 chk의 위치를 조정하고 마찬가지로 모든 점에 대해서 방문여부를 확인하고 BFS 절차를 시작되도록 했다.