백준 - 이분 그래프 (1707)

let fIO = FileIO()
let K = fIO.readInt()
var graph = [[Int]]()
var visited = [Bool]()
var group = [Int]()
var isYes = true

for _ in 0..<K {
    let V = fIO.readInt(), E = fIO.readInt()
    visited = Array(repeating: false, count: V + 1)
    group = Array(repeating: 0, count: V + 1)
    graph = Array(repeating: [], count: V + 1)
    // 인접 리스트 만들기
    for _ in 0..<E {
        let a = fIO.readInt(), b = fIO.readInt()
        graph[a].append(b)
        graph[b].append(a)
    }
    for v in 1...V {
        isYes = true
        dfs(v)
        if !isYes {
            break
        }
    }
    print(isYes ? "YES" : "NO")
}

func dfs(_ vertex: Int) {
    visited[vertex] = true
    for node in graph[vertex] {
        if !visited[node] {
            group[node] = (group[vertex] + 1) % 2
            dfs(node)
        } else {
            if group[node] == group[vertex] {
                isYes = false
            }
        }
    }
}

이분 그래프는 그래프의 정점을 두 집합으로 나누었을 때, 같은 집합에 있는 정점들이 서로 인접하지 않도록 만들 수 있는 그래프를 뜻한다.

그림으로 표현해보면 더 이해하기 쉬운데, 인접한 정점들은 서로 다른 색으로 칠해져 있음을 알 수 있다.

→ DFS 알고리즘을 실행하면서 나와 인접한 노드들에 다른 색을 칠해준다. 나와 인접하면서 이미 방문했던 노드 중 나와 같은 색으로 칠해져 있는 노드가 있다면 이분 그래프를 만들 수 없으므로 탐색을 종료한다.

→ 그래프의 모든 노드가 이어져 있음이 보장되어 있지 않기 때문에 모든 노드마다 DFS를 실행해야 한다.