[백준 1707] 이분 그래프

🍎 [백준 1707] 이분 그래프

 

문제링크

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

1707번: 이분 그래프

 

⚾ 코드 (PyPy3 제출)

from collections import deque
K = int(input())


def bfs(graph, i):
    q = deque()
    q.append(i)

    while q:
        now = q.popleft()
        for node in graph[now]:
            if visited[node] == visited[now]:
                return False

            if visited[node] == 0:
                # 방문하지 않았을 경우, 현재 노드의 값에 *-1
                visited[node] = visited[now]*(-1)
                q.append(node)
    return True


for _ in range(K):

    V, E = map(int, input().split())  # V: 정점의 개수, E, 간선의 개수

    visited = [0 for _ in range(V+1)]
    graph = [[] for _ in range(V+1)]
    result = "YES"
    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:
            visited[i] = 1
            if not bfs(graph, i):
                result = "NO"
                break

    print(result)

 

🔔 해결 과정 & 깨달은 점

- 이분 그래프 여부를 파악하기 위해 BFS 알고리즘을 쓰는 것이 가장 적당할 것이라고 판단했다.

- python으로 제출했을 때는 시간 초과가 뜨는데 PyPy3로 제출했을 때는 통과되었다.

- BFS를 구현할 때, 함수를 이용해 구현하는게 더 나은 것 같다.

- 처음에 코드를 아래와 같이 함수를 사용해서 구현하지 않고 for문 안에 하나로 구현했더니, break를 할 때 한 번에 빠져나오지 못하고 for문을 하나씩 빠져나오는 문제가 발생했다. 아래의 코드도 PyPy3로 했을 때 통과했지만, 코드의 간결성을 위해서라도 함수를 사용하는 것이 좋을 것 같다고 판단했다.

from collections import deque
K = int(input())

for _ in range(K):

    V, E = map(int, input().split())  # V: 정점의 개수, E, 간선의 개수

    visited = [0 for _ in range(V+1)]
    graph = [[] for _ in range(V+1)]
    result = "YES"
    q = deque()

    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:
            continue
        else:
            visited[i] = 1
            q.append(i)

            while q:
                now = q.popleft()

                for node in graph[now]:
                    if visited[node] == visited[now]:
                        result = "NO"
                        break

                    if visited[node] == 0:
                        # 방문하지 않았을 경우, 현재 노드의 값에 *-1
                        visited[node] = visited[now]*(-1)
                        q.append(node)

    print(result)