[백준] 1707번 : 이분 그래프 with python3

27 Sep 2018

Reading time ~2 minutes

문제: https://www.acmicpc.net/problem/1707

목표:

이분 그래프이면 true, 아니면 false

solution 설명 :

주 idea
- 한 번도 안 간 곳은 0
- 처음은 1, 그것과 연결된 애는 2를 준다.
dfs, bfs 모두 solution을 만들어봤다.
- bfs는 시간초과가 난다 ㅜ

dfs 방법 1

import sys
read = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(100000)

def colored_vertex(graph, colored, x, c):
    colored[x] = c
    for y in graph[x]:
        if colored[y] == 0: # 역시나 안간 곳이면
            colored_vertex(graph, colored, y, 3-c) # 2를 주고, 걔랑 연관 된 애는 또 1을 준다.


def make_graph(v, e):
    graph = {}
    for i in range(1,v+1):
        graph[i] = set()
    for j in range(e):
        a, b = map(int, read().split())
        graph[a].add(b)
        graph[b].add(a)
    return graph


def solution():
    v, e = map(int, read().split())
    graph = make_graph(v, e)
    colored = [0]*(v+1)
    ans = 'YES'

    for i in range(1, v+1):
        if colored[i] == 0: # 한번도 안 간 곳이면
            colored_vertex(graph, colored, i, 1) # 일단 1을 준다.
            # 1로 일단 무조건 하고 dfs속에서는 2하나만 하게하고 끝내는 건가

    for i in range(1, v+1):
        for j in graph[i]:
            if colored[i] == colored[j]:
                # i의 색(colored[i])이 i에 연결됬던 j와 같으면 no
                ans = 'NO'
                break

    return ans

for i in range(int(read())):
    print(solution())

dfs 방법 2

import sys
read = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(100000)

# 양 끝점의 색이 같은지 다른지를 확인하는 게 없어진다.

def dfs(graph, color, start, c):
	color[start] = c
	for node in graph[start]:
		if color[node]==0:
            # 지나간 것
			if dfs(graph, color, node, 3-c) == False:
                # 지나간 거여서 그 애와 연관된 애들 것을 확인했는데
                # 밑에 else쪽에서 나온 것이 False로 나옴으로 이것은 False를 줘야한다.
				return False
		else:
			if color[node] == color[start]:
        # 다음 정점 색과 현제 정점의 색이 같으면 이건 false
				return False
	return True


for _ in range(int(read())):
    v, e = map(int, read().split())
    graph = {}
    for i in range(1,v+1):
        graph[i] = set()
    for j in range(e):
        a, b = map(int, read().split())
        graph[a].add(b)
        graph[b].add(a)

    color = [0]*(v+1)
    ok = 'YES'
    for i in range(1,v+1):
    	if color[i]==0:
            # 안간노드만 확인
            if dfs(graph, color, i, 1) == False:
                ok = 'NO'
                break
    print(ok)

bfs 방법(시간초과)

import sys
read = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(100000)

def solution():
    v, e = map(int, read().split())
    graph = {}
    for i in range(1,v+1):
        graph[i] = set()
    for _ in range(e):
        a, b = map(int, read().split())
        graph[a].add(b)
        graph[b].add(a)

    colored = [0]*(v+1)
    ans = 'YES'

    queue = []
    for i in range(1, v+1):
        if colored[i] != 0: continue

        queue.append(i)
        while queue:
            for j in range(0, len(queue)):
                current = queue.pop(0)
                adjcolor = 0
                for next in graph[current]:
                    if colored[next] ==  0:
                        queue.append(next)
                    else:
                        if adjcolor == 0:
                            adjcolor = colored[next]
                        elif adjcolor != colored[next]:
                            ans = 'NO'
                if adjcolor == 0:
                    colored[current] = 1
                else:
                    colored[current] = 3-adjcolor

    return ans

for _ in range(int(read())):
    print(solution())

algorithm 백준