[백준] 1707번 이분 그래프 (by Python)

 

문제

처음에 이분 그래프의 정확한 의미를 모르겠어서 조금 헤맸지만 결국 핵심은 각 노드가 인접한 노드들과 다른 색깔을 가지고 있으면서, 총 2가지 색깔로 다 표현할 수 있는 그래프 라고 생각하면 될 것 같다. 이전의 연결 요소의 개수를 찾는 문제에서 BFS 방법보다 DFS 방법이 더 시간이 낮게 나오는 것을 확인하고 DFS로 들이댔지만 풀고 나니 BFS로 푸는 것이 더 나은 문제였다는 생각이 들어 BFS로도 풀어봤다. 그리고 DFS로 풀려면 sys.setrecursionlimit()을 일단 크게 줘야겠다는 교훈을 얻게 된 문제!

 

첫 번째 풀이 (by DFS)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

k = int(input())

def dfs(v, num):
    global visited
    global graph

    visited[v] = num
    for adj in graph[v]:
        if visited[adj] == 0:
            dfs(adj, -num)


for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v + 1)]
    visited = [0 for _ in range(v + 1)]

    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    for i in range(1, v + 1):
        if visited[i] == 0:
            dfs(i, 1)

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

 

개인적으로는 마지막에 출력할 때 all 함수를 쓴 게 스스로 좀 만족스러운 부분이다. 저런 기능이 있으면 좋겠다고 막연히 떠올릴 때가 많았는데 파이썬에는 이미 구현되어 있었다. 역시 파이썬... 언젠가 C++로도 알고리즘을 연습해볼 생각이지만 많이 그리워하게 되지 않을까? 하는 생각. 그리고 setrecursionlimit()을 20000까지 주었는데 RecursionError가 나서 그냥 코드가 잘못됐나 까지 생각했지만 100000 주니까 해결됐다는 이야기.... 하하

 

두 번째 풀이 (by BFS)

 

from collections import deque
import sys
input = sys.stdin.readline

def bfs(v):
    visited[v] = 1
    q = deque([v])

    while q:
        temp = q.popleft()
        for adj in graph[temp]:
            if visited[adj] == 0:
                visited[adj] = -visited[temp]
                q.append(adj)
            elif visited[adj] == visited[temp]:
                return False
    return True

k = int(input())

for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v + 1)]
    visited = [0 for _ in range(v + 1)]
    flag = True

    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    for i in range(1, v + 1):
        if visited[i] == 0:
            if not bfs(i):
                flag = False
                break

    print("YES" if flag else "NO")

 

BFS로 풀면 DFS 함수에서는 recursion을 사용하기에 return을 쓰기 애매했던 점이 해소되어 조기에 문제를 발견하고 모두 검사를 하지 않고 해결할 수 있단 장점이 있다. 실제로도 시간이 덜 들었다:)