[Python] 1707번 이분 그래프

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

1707번: 이분 그래프

---

 

22/11/14

 

 

전형적인 BFS, DFS응용 문제로, 이분 그래프에 대한 정의를 잘 알고 있기만 한다면 쉽게 풀 수 있는 문제이다.

 

이 문제에서는 BFS로 접근했으며, DFS로는 조금 귀찮을 것 같아 DFS로는 접근하지 않았다.

 

의외로 조금씩 틀렸었던 문제로, 문제를 잘 읽는 습관을 기르도록 하자.

---

 

문제 접근 방식:

 

 

처음에는 이분 그래프의 정의를 헷갈려서 틀렸습니다를 받았다.

 

어떤 식으로 이해했었냐면, 이분 그래프의 원래 정의에 조금 더 강화된 정의, 즉, 모든 점이 서로 연결돼있어야 한다고 생각했었기 때문에 몇 번 WA를 받았었다.

 

옳은 접근 방법은 아래와 같다.

 

문제에 나와 있는 이분 그래프의 정의, 즉, "정점들을 두 개의 집합으로 나누고, 각 집합에 속한 정점들끼리는 서로 인접하지 않도록 분할할 수 있는 그래프"라고 나와있었기 때문에 한 정점을 무작위로 잡고, 그 정점을 1로 색칠하였다.(방문처리를 하는 배열에 1을 넣었다.)

 

그 정점과 연결된 모든 정점들은 서로 인접한 정점들이므로, 즉, 다른 집합에 속해있는 정점들 이므로, 2로 색칠하도록 했다.

 

BFS이므로 이제 방금 전에 2로 색칠했었던 모든 정점에 대해 색칠하기(탐색하기)를 진행한다.

 

2와 연결된 모든 정점들은 1로 색칠되어있어야 된다. 따라서, 현재 2와 연결돼있는 정점 중, 방문처리가 안된 곳을 1로 전부 색칠하도록 했다.

 

이를 모든 노드가 2로 색칠될 때까지 반복하였다.

 

이후 색칠된 노드의 인접 리스트에 있는 모든 숫자들이 색칠된 노드와 전부 다 다른 숫자인지 확인하는 과정을 거쳤다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1707번 이분 그래프
# 그래프 이론, 그래프 탐색, BFS, 이분 그래프
'''
접근 방법:
BFS를 돌릴 때 한 정점의 인접 정점은 다른 색으로 칠함
'''
import sys
input = sys.stdin.readline
from collections import deque

def BFS(start):
    queue = deque()
    queue.append(start)
    visited[start] = 1
    while queue:
        now_node = queue.popleft()
        color = 0
        if visited[now_node] == 1:
            color = 2
        elif visited[now_node] == 2:
            color = 1
        for near_node in graph[now_node]:
            if visited[near_node] == 0:
                visited[near_node] = color
                queue.append(near_node)
K = int(input())
for _ in range(K):
    V, E = map(int, input().rstrip().split())
    graph = [[] for _ in range(V+1)]
    visited = [0 for _ in range(V+1)]
    for _ in range(E):
        u, v = map(int, input().rstrip().split())
        graph[u].append(v)
        graph[v].append(u)
    flag = True
    for i in range(1, V+1):
        if visited[i] == 0:
            BFS(i)
    for node in range(1, V+1):
        S = set(visited[i] for i in graph[node])
        if visited[node] == 1:
            if 1 in S:
                flag = False
                break
        elif visited[node] == 2:
            if 2 in S:
                flag = False
                break
    print('YES' if flag else 'NO')