1707번: 이분 그래프 (DFS/BFS)

1707번: 이분 그래프

만약 연결 그래프라면 노드 1에서 부터 탐색을 시작해서 총 2가지 색을 이용해 인접 노드를 자신과 다른 색으로 색칠한다. 이때 이분 그래프를 만들때는 색깔을 기준으로 노드를 분류하면 된다. 만약 어떤 노드의 색과 그 노드의 인접 노드의 색이 같은 것이 있다면 이분 그래프는 불가능하다. 연결 그래프가 아니라면 색칠된 수와 전체 노드의 수를 비교했을 때 이 둘이 다를 경우이다. 따라서 이때는 노드 1에서 시작하지 말고 다른 노드들에서 시작해서 동일한 색칠을 진행하여 판단한다. 아래는 이 아이디어를 BFS를 이용해 구현한 것이며 , 시간 초과가 뜬 코드이다.

import sys
sys.setrecursionlimit(100000)
from collections import deque
k = int(input())
for _ in range(k):
    v,e = map(int,input().split())
    graph = [[] for i in range(v+1)]
    for i in range(e):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)

    def bfs(graph,start,v):
        visited = [0]*(v+1)
        queue = deque([start])
        visited[start] = 1
        while queue:
            v = queue.popleft()
            v_color = visited[v]
            for i in graph[v]:
                if visited[i] == 0:
                    queue.append(i)
                    visited[i] = 2 if v_color==1 else 1
                elif visited[i] == v_color:
                    return -1
        return visited
    def solve(v):
        for i in range(2,v+1):
            s = bfs(graph,i,v)
            if s == -1:
                return -1
    o = bfs(graph,1,v)
    if o == -1:
        print('NO')
    else:
        cnt = 0
        for i in o:
            if i != 0:
                cnt+=1
        if cnt != v:
            if solve(v) == -1:
                print('NO')
            else:
                print('YES')
        else:
            print('YES')

아마 연결 그래프가 아닌 경우에 BFS를 반복해서 진행하는 과정에서 많은 연산을 하였기 때문이라고 생각한다. 현재 BFS로 구현한 코드는 연결 그래프가 아닌 경우에 빠르지 않으며 연결 그래프가 아닌 점을 확인하고 또 이후에 경우를 따져서 판단을 하기 복잡하다. 따라서 연결 그래프가 아닐때 한번 탐색(색칠)을 진행했을 때 탐색을 진행하지 않은 지점을 시작노드로 탐색을 하여 탐색을 하는 알고리즘을 DFS를 이용해 구현했으며 맞았다. 

import sys
sys.setrecursionlimit(100000)
from collections import deque
k = int(input())
for _ in range(k):
    v,e = map(int,input().split())
    graph = [[] for i in range(v+1)]
    for i in range(e):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    visited = [0]*(v+1) # 탐색을 하기 전 상황은 0 으로 초기화 
    def dfs(graph, v, visited,color):
        # 만약 이전 노드의 color가 2이면 1로 색칠, 1이면 2로 색칙
        visited[v] = 1 if color== 2 else 2
        color = visited[v]
        # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for i in graph[v]:
            if visited[i] == 0:
                dfs(graph, i, visited,color)
        return visited
    visited = dfs(graph,1,visited,2) # 노드 1에서 부터 DFS 진행
    for i in range(2,v+1): 
        if visited[i] == 0: # 만약 색칠되지 않은 노드가 있으면 
            visited = dfs(graph,i,visited,2) # 해당 노드에서 부터 DFS
    def solve():
        for i in range(1,v+1):
            for j in graph[i]:
                # 한 노드의 색과 인접 노드의 색이 같으면 'NO'
                if visited[i] == visited[j]: 
                    return 'NO'
        return 'YES'
    print(solve())

dfs와 bfs의 시간차이가 그리크지 않다면 dfs로 구현한 코드에서 색칠되지 않은 노드가 있을 때(연결 그래프가 아닐때) 처리한 부분을 그대로 구현한다면 성공해야 할 것이다. 그리고 BFS 코드에서 수정해보았다. 결과는 성공적이었다. 따라서 최종적으로 bfs, dfs를 이용해 구현한 코드는 아래와 같다.  

import sys
sys.setrecursionlimit(100000)
from collections import deque
k = int(input())
for _ in range(k):
    v,e = map(int,input().split())
    graph = [[] for i in range(v+1)]
    for i in range(e):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    visited = [0]*(v+1) # 탐색을 하기 전 상황은 0 으로 초기화

    def dfs(graph, v, visited, color):
        # 만약 이전 노드의 color가 2이면 1로 색칠, 1이면 2로 색칙
        visited[v] = 1 if color == 2 else 2
        color = visited[v]
        # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for i in graph[v]:
            if visited[i] == 0:
                dfs(graph, i, visited, color)
        return visited

    def bfs(graph,start,visited):
        queue = deque([start])
        visited[start] = 1
        while queue:
            v = queue.popleft()
            color = visited[v]
            for i in graph[v]:
                if visited[i] == 0:
                    queue.append(i)
                    visited[i] = 1 if color== 2 else 2
        return visited

    #visited = dfs(graph,1,visited,2) # 노드 1에서 부터 DFS 진행
    visited = bfs(graph,1,visited)
    for i in range(2,v+1):
        if visited[i] == 0: # 만약 색칠되지 않은 노드가 있으면
            #visited = dfs(graph,i,visited,2) # 해당 노드에서 부터 DFS
            visited = bfs(graph,i,visited)
    def solve():
        for i in range(1,v+1):
            for j in graph[i]:
                # 한 노드의 색과 인접 노드의 색이 같으면 'NO'
                if visited[i] == visited[j]:
                    return 'NO'
        return 'YES'
    print(solve())