이분 그래프 판별_BFS

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 그래프의 같은 집합의 노드에 간선이 존재하는지 판단하기 위해서는 그래프를 하나하나 탐색해 봐야 함
• 따라서 너비우선탐색을 통해 노드를 방문하고, 여기서 같은 집합인지 아닌지는 처음부터 알 수 없으므로
• 노드의 번호마다 그룹(0 혹은 1)을 부여하는 배열을 통해 같은 집합인 것을 확인할 수 있음
• 노드를 방문할 때, 현재 연결된 노드의 그룹이 1이라면 0을, 0이라면 1을 부여함으로써 집합을 관리할 수 있고,
• 여기서 같은 집합이라면, 노드끼리 연결되어 있으면 안되기 때문에 현재노드와 인접한 노드 중에 그룹이 같은 것이 있다면
• 이분 그래프가 될 수 없음. 따라서 O(N + M)의 시간복잡도로 문제를 해결

5. 전체 코드

//MARK: - 이분 그래프 판별 - BFS

//MARK: - Framework
import Foundation

//MARK: - Type
struct Graph {
    //MARK: - Property
    var edges: [Int]
    
    //MARK: - Initializer
    init() {
        self.edges = []
    }
}

//MARK: - Variable
var graph: [Graph] = []
var visited: [Bool] = []
var groups: [Int] = []

//MARK: - Function
func bfs(_ start: Int) -> Bool {
    var result: Bool = true
    var queue: [Int] = []
    queue.append(start)
    visited[start] = true
    
    while !queue.isEmpty {
        let current: Int = queue.removeFirst()
        
        for i in stride(from: 0, to: graph[current].edges.count, by: 1) {
            let next: Int = graph[current].edges[i]
            
            if !visited[next] {
                visited[next] = true
                queue.append(next)
                groups[next] = groups[current] == 0 ? 1 : 0
            } else {
                if groups[next] == groups[current] {
                    result = false
                    break
                }
            }
        }
        
        if !result {
            break
        }
    }
    
    return result
}

func solution() -> Void {
    //MARK: - Input
    guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
    let N: Int = input.map { Int($0) }[0] ?? 0
    let M: Int = input.map { Int($0) }[1] ?? 0
    graph = Array(repeating: Graph(), count: N + 10)
    visited = Array(repeating: false, count: N + 10)
    groups = Array(repeating: 0, count: N + 10)
    
    for _ in 0..<M {
        guard let data: [String] = readLine()?.components(separatedBy: " ") else { return }
        let a: Int = data.map { Int($0) }[0] ?? 0
        let b: Int = data.map { Int($0) }[1] ?? 0
        
        graph[a].edges.append(b)
        graph[b].edges.append(a)
    }
    
    //MARK: - Process & Output
    print(bfs(1) ? "Yes" : "No")
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.