[백준] 1707번 : 이분 그래프 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1707번: 이분 그래프

 

1. 문제 설명

2. 풀이과정

노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 적절하게 임의로 분할할 수 있다고 한다.

트리의 경우에는 항상 이분 그래프가 된다는 것을 알 수 있는데, 사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문이다.

하지만 사이클이 발생했을 때 이분 그래프가 불가능할 수도 있다.

이런 경우에는 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 되었을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능하다는 것으로 판별할 수 있다.

 

입력된 그래프 데이터를 인접 리스트로 구현한다.

모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행한다.

DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별한다.

실행 결과가 이분 그래프가 아니면 이후 노드는 탐색하지 않는다.

탐색이 끝나면 이분 그래프 여부를 정답으로 출력한다.

※ 코드에 sys.setrecursionlimit(10 ** 6)를 앞부분에 추가해 주면 RecursionError가 발생하지 않는다.

 

슈도코드

1. K(테스트 케이스 개수) 입력받기
2. for K만큼 반복:
   1. V(노드 개수), E(에지 개수) 입력받기
   2. graph(그래프 데이터 저장 인접 리스트)
   3. for E만큼 반복:
      1. S(에지와 노드 1), E(에지와 노드 2) 입력받기 
      2. graph 인접 리스트에 그래프 데이터 저장하기
   4. DFS 구현하기 DFS(v):
      1. visited 리스트에 현재 노드 방문 기록하기
      2. for 현재 노드와 연결 노드 반복:
         1. if (현재 노드의 연결 노드 중 방문하지 않은 노드):
            1. 현재 노드와 다른 집합으로 연결 노드 집합 저장
            2. DFS(연결 노드) 실행
         2. elif (이미 방문한 노드인데, 현재 나의 노드와 같은 집합): 이분 그래프 아님
   5. EvenGraph(이분 그래프 판별 변수)
   6. visited(방문 기록 저장 리스트)
   7. check(노드별 집합 저장 리스트)
   8. for V만큼 반복:
      1. if (아직 이분 그래프 가능성이 있으면): DFS(현재 노드) 실행
      2. else: 판별 종료
   9. if (이분 그래프이면): YES 출력
   10. else: NO 출력

반응형

3. 소스코드

import sys
sys.setrecursionlimit(10 ** 6)

K = int(sys.stdin.readline())
for _ in range(K):
    V, E = map(int, sys.stdin.readline().split())

    graph = [[] for _ in range(V + 1)]
    for _ in range(E):
        S, E = map(int, sys.stdin.readline().split())
        graph[S].append(E)
        graph[E].append(S)

    def DFS(v):
        global EvenGraph
        visited[v] = False
        for i in graph[v]:
            if (visited[i]):
                check[i] = (check[v] + 1) % 2
                DFS(i)
            elif (check[v] == check[i]):
                EvenGraph = False

    EvenGraph = True
    visited = [True] * (V + 1)
    check = [0] * (V + 1)
    for i in range(1, V + 1):
        if (EvenGraph):
            DFS(i)
        else:
            break

    if (EvenGraph):
        print('YES')
    else:
        print('NO')