[PYTHON] 백준 1707 - 이분 그래프

성능 요약

메모리: 230372 KB, 시간: 1288 ms

분류

너비 우선 탐색, 이분 그래프, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

---

아이디어, 문제풀이

• 이분그래프의 정의를 확실하게 알아야만 풀 수 있는 문제
• 한번씩 깊이 들어갈때마다, color로 지정한 배열에 1, -1 을번갈아 출력하며 색을 지정해준다.
• 이 dfs를 모든 정점에 대해 돌려주는데, 만약 다음 깊이에 들어갔을때 color끼리의 색이 다르다면 이분그래프가 아니다.
• 모든 정점에서 시작했을때 완벽하게 위 조건을 만족해야지만 이분 그래프가 된다.

---

TROUBLE SHOOTING

• 이분그래프… 일단 어렵다. 많은 시간을 투자했지만 완벽하게 이분그래프를 파고들진 못했다. 문제풀이를 진행할 수 있을 수준까지만 학습한 뒤 바로 코드 구현에 들어갔다.

  아이디어에 적혀있는 내용이 거의 전부라고 볼 수 있는데, 저 코드를 구현해 내는게 당시에는 만만치 않았다. 이전 컬러와 같다는건 -color 이 되야한다는 점인데, 너무 급하게 이론을 이해하고 풀이를 하다보니 저런 사소한 부분들도 놓치며 코딩을 했던 기억이 난다.
  

• 이 문제의 변별력? 과 같은 포인트는 모든 정점에서 체크를 해준다는 점인데, 실제로 예외 상황들을 그림을 그려가며 체크해보니 이해가 됐다. 말로만 설명을 들어선 이해할 수 없는 이분 그래프… 이분 그래프의 알고리즘이 나오게 된 계기가 있을텐데, 그 자료를 완벽하게 찾아내진 못했다. 그래도 전 과정을 이해하며 코드를 구현했음에 만족한다!

• 이 코드상에서 내가 dfs 문 안의 return 값을 문자열 "YES”, "NO” 로 지정했는데, 이게 진짜 불편했다.

      while stack:
          
          node, color = stack.pop()
  
          if visit[node] == 0:
              visit[node] = 1
              colors[node] = color
              for value in graph[node]:
                  stack.append((value, -color))
          
          #no가 나오는경우는 그전의 색과 같을때!
          elif colors[node] == -color: 
              return "NO"
          
          else:
              continue
  
      return "YES"

  차라리 posible이라는 변수를만들고 0, 1 로 나눴다면 내 기준에서 더 쉽게 구현할 수 있었을것 같다. 저당시에 저 헷갈림을 어떻게 참았는지 모른다 ;ㅁ; 나한테 맞는 문제 풀이법을 찾아내는게 문제풀이들의 핵심 요소인것 같다는 생각이 들었다.
  

---

코드

#https://www.acmicpc.net/problem/1707
#이분 그래프
#1707

import sys
# input = sys.stdin.readline

k = int(input())

full_graph = []

for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    # print(graph)
    full_graph.append(graph)

# print(full_graph)

# visit = [0] * (v+1)
# color = [0] * (v+1)

def dfs(graph, start, visit, colors): #color은 트리거 / 1은 1집합, -1은 2집합

    # for i in graph[start]:
    #     if visit[i] == 0:
    #         visit[i] = 1
    #         color[i] = color 
    #         dfs(graph, i, visit, -color)

    stack = [(start, 1)]
    
    while stack:
        
        node, color = stack.pop()

        if visit[node] == 0:
            visit[node] = 1
            colors[node] = color
            for value in graph[node]:
                stack.append((value, -color))
        
        #no가 나오는경우는 그전의 색과 같을때!
        elif colors[node] == -color: 
            return "NO"
        
        else:
            continue

    # print(visit)
    # print(colors)

    return "YES"

# for graph in full_graph:
#     v = len(graph) - 1
#     visit = [0] * (v+1)
#     colors = [0] * (v+1)

#     print(dfs(graph, 1, visit, colors))

for graph in full_graph:
    v = len(graph) - 1
    visit = [0] * (v+1)
    colors = [0] * (v+1)

    answer = "YES"

    #1에서만 체크하는게 아니라, 모든 점에서 만족하는지의 여부를 알아야 하기에,
    #for문을 활용해 모두 체크해준다
    for node in range(1, v+1):
        if visit[node] == 0:
            result =dfs(graph, node, visit, colors)
            if result == "NO":
                answer = "NO"
    
    print(answer)