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

문제 링크 : https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

DFS 응용력을 길러준 문제이다.

DFS로 탐색을 진행하면서 빨강 / 파랑으로 번갈아서 색칠을 한다고 가정하였다.

 

Red / Blue 색칠공부

 

색칠 탐색을 끝낸 후에, 인접 리스트 그래프에서 자신과 같은 색깔로 칠해진 인접 노드가 있는지 확인한다.

인접 노드 중에 같은 색깔로 칠해진 노드가 있다면, 이분 그래프를 생성할 수 없다.

 

주의할 점 :

1. 1번 노드에 대해서만 DFS를 진행해서는 안된다. 주어진 그래프가 연결 그래프라는 보장이 없기 때문이다.

2. 입력 데이터가 많기 때문에, 파이썬으로 코드를 제출할 경우 반드시 sys.stdin.realine()을 활용 해야한다.

3. setrecursionlimit 으로 재귀 함수 호출 리밋을 해제해줘야 한다.

4. pypy로 제출할 경우 메모리 초과가 나지만, python3로 제출할 경우 통과한다.. 

( 5. "Yes"로 출력하는 것이 아니라 "YES"로 출력하는 것이다. 바보같이 이거 땜에 시간 엄청 날렸다 ,, )

 

😊 정답 코드

import sys

sys.setrecursionlimit(10 ** 6)

K = int(sys.stdin.readline())


def dfs(graph, visit, node, color):
    visit[node] = color

    for x in graph[node]:
        if visit[x] == 'None':
            if color == 'Red':
                dfs(graph, visit, x, 'Blue')
            elif color == 'Blue':
                dfs(graph, visit, x, 'Red')


while K > 0:
    V, E = map(int, sys.stdin.readline().split())

    graph = [[] for _ in range(V + 1)]
    visit = ['None'] * (V+1)

    for _ in range(E):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    for x in range(1, V + 1):
        if visit[x] == 'None':
            dfs(graph, visit, x, 'Red')

    check = True

    for node in range(1, V+1):
        for x in graph[node]:
            if visit[node] == visit[x]:
                check = False
                break

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

    K -= 1