[백준/Python] 1707번: 이분 그래프

📖  문제 링크

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

1707번: 이분 그래프

 

👩‍💻  문제풀이

 

이분 그래프란 간단히 말해서, 한 간선의 양쪽 정점이 각각 다른 색(그룹) 이어야 한다는 것! 

아래의 두 그래프를 보자.

왼쪽 그래프는 한 간선에 빨강, 파랑 점이 하나씩 연결된 반면(이분그래프),

오른쪽 그래프는 주황색 화살표가 가리키는 간선이 빨강-빨강 점으로 연결된 것을 알 수 있다(이분 그래프가 아님).

 

이러한 특징을 염두에 두고 DFS로 풀이를 시작했지만 도저히 풀리지 않았고 ^^ 블로그와 강의의 도움을 받았다.

DFS함수에 color 변수를 함께 입력해주어 간선에 연결된 정점의 색상이 같은 경우 False를 반환하여 No를 출력하는 방식이었다. 

 

기본 DFS함수에 몇 줄 더 추가한 것 같은데, 왜 혼자 하면 생각이 잘 안 나는지 모르겠고....ㅎㅎ..

 

그리고 계속해서 런타임 에러가 발생하여 확인해보니 파이썬 재귀 함수 제한이 걸려

지난번 공부했던 함수를 추가해주었다. 

sys.setrecursionlimit(100000)

 

 

여러 번의 시도 끝에 성공! 

 

 

✅  최종 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)  #크게 줘야함

n = int(input())
def dfs(x, color):
    check[x] = color
    for i in arr[x]:
        if check[i] == False:
            a = dfs(i, -color)
            if not a:
                return False
        elif check[i] == check[x]:
            return False
    return True
        
    
for _ in range(n):
    v, e = map(int, input().split())
    check = [False] * (v+1)
    arr = [[] for _ in range(v+1)]
    for i in range(e):
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)
        
    for i in range(1, v+1):
        if check[i] == False:
            result = dfs(i, 1)
            if result == False:
                break
            
    print("YES" if result else "NO")