[백준알고리즘] 1707번: 이분 그래프 -Python

[백준알고리즘] 1707번: 이분 그래프 -Python

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

1707번: 이분 그래프

20200424

아래에 새로 푼 코드를 첨부했다. 기존의 코드는 객체를 생성하다보니 기존의 코드보다 빠르다.

---

이분 그래프(Bipartite Graph)가 설명이 무슨말인지 모르겠어서 찾아봤다. 이분 그래프 위키를 참고하자.

간단하게 말하자면 각 정점을 칠할 수 있는 빨간색과 파란색이 존재할 때 인접한 두 정점을 반드시 다른 색으로 칠할 수 있는지를 물어보는 문제이다.

뭔가 레드블랙트리를 보는 것 같았다.

 

아무튼 이 문제를 푸는데 반례를 참고한 것이 있다. 아래처럼 그래프가 독립적으로 존재하는 경우가 그렇다.

1
5 4
1 2
1 3
2 3
4 5

 

coloring을 하기 위해서 DFS와 BFS방식이 존재할 수 있다. 많은 분들이 DFS를 이용해서 이동하면서 직접 coloring 한 것 같은데, 나는 BFS를 이용했었다. 레벨별로 같은 색을 칠하도록 했다.

 

입력받은 연결 정보를 유지하기 위해서 table이라는 리스트를 만들었고, 각 정점의 방문여부를 표시하는 리스트 visited와 각 정점의 색을 구분하는 리스트 color를 만들었다. DFS로 문제를 해결할 경우 색칠하면서 이동하기 때문에 visited에 값으로 구분하면서 color를 구분할 수도 있겠지만, BFS를 이용하면서 방문하기 전에 색을 칠했기 때문에 두 개의 리스트를 이용했다.

 

#### 다음에 위치한 반복문이 바로 위에서 찾은 반례 때문에 추가한 코드다.

 

정리하면 방문하지 않은 정점부터 시작해서 BFS탐색을 한다. 해당 정점에서 이동이 가능한 모든 정점에 현재의 색과 다른 색(코드 상으로는 1과 -1로 구분했다.)을 칠하고 큐(덱)에 넣는다. 큐에서 하나씩 poll 하게 된 정점은 그때 방문한 상태가 되며 coloring을 반복한다.

 

이 coloring과정에서 연결된 vertex가 coloring이 되지 않는 상태라면 문제가 없지만, coloring이 같은 색이 아닌 다른 색으로 되어있다면 더이상 coloring을 종료하고 이분 그래프가 될 수 없는 상태임을 출력한다.

import sys
from collections import deque

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

for _ in range(testcase):
    v, e = map(int, sys.stdin.readline().split())
    table = [[] for _ in range(v+1)]
    visited = [0] * (v+1)
    color = [0] * (v+1)
    YES_FLAG = True

    for __ in range(e):
        v1, v2 = map(int, sys.stdin.readline().split())
        table[v1].append(v2)
        table[v2].append(v1)

    def check(vertex):
        global YES_FLAG, visited, color
        color[vertex] = 1
        queue = deque([vertex])  
        while queue and YES_FLAG:
            s = queue.popleft()
            c = color[s]
            
            if visited[s]:
                continue

            visited[s] = 1
            for link in table[s]:
                if visited[link] and color[s] == color[link]:
                    YES_FLAG = False
                    break
                elif not visited[link]:
                    color[link] = -c
                    queue.append(link)
    
    ####
    for i in range(1, v+1):
        if not YES_FLAG:
            break
        if not visited[i]:
            check(i)

    if YES_FLAG:
        sys.stdout.write("YES\n")
    else:
        sys.stdout.write("NO\n")

20200424

새롭게 푼 방법이다. 마찬가지로 BFS를 이용해주었다.

하지만 이 코드의 경우에는 PyPy3는 통과하지만 Python3는 시간초과가 발생했다. 혹시나 하고 input()을 sys.stdin.readline()으로 바꿔주니 위의 코드보다 빠른 시간 안에 통과했다.

 

문제를 새로 풀 때 어려움을 겪었던 것은 연결이 되어있지 않은 그래프였다. 처음에는 연결이 안되어있더라도 노드가 하나만 있는 것으로 생각을 했었기 때문에 이 부분은 아무집합이나 넣어주면 되기 때문에 상관이 없을 것 같았다.

이건 잘못된 생각이었는데, 두 노드 이상으로 구성된 연결된 서브그래프를 갖는 그래프가 주어지면 두 서브 그래프 모두 검사를 해주어야 한다.

from collections import deque
import sys

for tc in range(int(sys.stdin.readline())):
    v, e = map(int, sys.stdin.readline().split())
    link = [[] for _ in range(v+1)]
    for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        link[a].append(b)
        link[b].append(a)
    
    color = [0] * (v+1)
    STOP = False
    for i in range(1, v+1):
        if STOP: break
        if color[i] > 0: continue

        color[i] = 1
        queue = deque([i])

        while queue and not STOP:
            q = queue.popleft()
            c = 3 - color[q]
            
            for l in link[q]:
                if color[l] == 0:
                    color[l] = c
                    queue.append(l)
                elif color[l] == color[q]:
                    STOP = True
                    break

    print("YES" if not STOP else "NO")

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다