[백준] 1707: 이분그래프

이분탐색, dfs

문제 : 이분탐색

육각보드
이 문제 처럼 이분탐색으로 풀면 되는 문제이다.
그래서 이 문제 또한 색칠 할 수 있는 가짓수를 구해서 3가지 이상이면 "NO"를 출력하고 탐색을 끝냈다.
글로벌 설정 안해주면 메모리 초과 나니 조심!

이분 그래프
다른 분이 푼 문제도 한번 보았는데 all 함수를 이용해 신선하게 푸셔서 가지고 와봤다. 이 분도 나와 같은 방식으로 푸셨는데, 마지막 출력 부분에서
값이 저장된 리스트를 돌면서 전부 다 다르면 "YES"를 출력하도록 했다.
이 때 all 함수를 이용해 전부 다 다르면을 구현하는 것이 신선했다.
all 함수를 이중배열에 쓰려면 람다식이 필수인 것 같다.

내 풀이

import sys
# 뎁스 오류 방지 
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
t = int(input())
def dfs(end, c):
	global ans
	global graph
	global visited
    	# 값 넣어주기 
	visited[end] = c
    	# 인접 노드가 나와 같으면 색깔이 하나 더 필요 
	if ans >= 3:
		return
    	# 한가지 색 필요
	ans = max(ans, 1)
	for i in graph[end]:
		if visited[i] == -1:
        		# 인접 노드는 한가지 색이 더 필요 -> 여기까지는 이분 그래프 
			dfs(i, 1-c)
			ans = max(ans, 2)
        	# 세가지 색 필요 -> 이분 그래프 아님 -> 리턴 
		elif visited[i] == c:
			ans = max(ans, 3)
			return
	return ans
for i in range(t):
	ans = 0
	result = 0
	n, m = map(int, input().split())
	graph = [[] for _ in range(n+1)]
	visited = [-1] * (n+1)
	for j in range(m):
		a, b = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	for i in range(1, n+1):
		if visited[i] == -1:
			dfs(i, 0)
            		# 모든 그래프가 연결되어 있지 않을 수도 있으므로 dfs를 돌 때마다 갱신
			result = max(ans, result)
	if result == 2:
		print('YES')
	else:
		print('NO')

다른 분의 풀이

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
t = int(input())
ans = 0
#이분탐색 코드 
def dfs(end, c):
	global visited
	global graph
	visited[end] = c
	for i in graph[end]:
		if visited[i] == -1:
        		#0과 1을 반복해서 넣어줌 
			dfs(i, 1-c)
for i in range(t):
	n, m = map(int, input().split())
	visited = [-1] * (n+1)
	graph = [[] for _ in range(n+1)]
	for j in range(m):
		a, b = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	for i in range(1, n+1):
		if visited[i] == -1:
			dfs(i, 1)
	# wow!!!
	print("YES" if all(all(visited[i] != visited[j] for j in graph[i]) for i in range(1, n+1)) else "NO")

람다식은 위대하다

"YES" if all(all(visited[i] != visited[j] for j in graph[i]) for i in range(1, n+1)) else "NO"