BOJ-1707 이분 그래프 Swift

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. 

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

내가 푼 풀이

접근방법: BFS

이 문제는 이분그래프의 성질을 이해하고 있다면 더 쉽게 풀 수 있습니다.

저는 이분그래프의 성질을 알고 나서 풀었습니다..

 

이분그래프의 성질은 인접한 점끼리는 서로 다른 집합이어야합니다.

집합1: [1,3] , 집합2: [2,4] 으로 위 그래프는 이분그래프입니다.

위 그래프는 2번과 인접한 점 [1, 3, 4]이 있습니다.

두개의 집합으로 분할했을 때, [1,3,4], [2]로 나눌 수 있지만 3번과 4번이 서로 인접한 관계이므로 이분그래프가 될 수 없습니다.

 

위 성질을 이용해 BFS탐색을 통해 현재지점과 인접한 지점을 다른 집합으로 분리한다.

탐색을 진행하며 현재노드와 인접한 노드가 같은 집합으로 속한다면, 해당 그래프는 이분그래프가 아니라고 판단한다.

 

예제그래프)

 

- 현재노드 1번 - 인접노드 2번

결과: [1], [2]

- 현재노드 2번 - 인접노드 1번, 3번, 4번

1번은 이미 다른집합으로 분리되었다.

결과: [1,3,4], [2]

- 현재노드 3번 - 인접노드 2번, 4번

현재노드인 3번과 인접노드 4번이 이전 탐색을 통해 같은 집합으로 저장되어 있었다.

결과 -> 이분그래프가 아님.

 

코드로 구현하면 다음과 같다

import Foundation

// 테스트케이스 수
let K = Int(readLine()!)!

for i in 0..<K {
    // 입력받기
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let V = input[0], E = input[1]
    var graph = [Int: [Int]]()
    for j in 0..<E {
        let input = readLine()!.split(separator: " ").map{Int(String($0))!}
        if graph[input[0]] == nil {
            graph[input[0]] = [input[1]]
        } else {
            graph[input[0]]?.append(input[1])
        }
        if graph[input[1]] == nil {
            graph[input[1]] = [input[0]]
        } else {
            graph[input[1]]?.append(input[0])
        }
    }
    
    var visited = Array(repeating: 0, count: V+1)
    var isBinaryGraph = true
    
    // BFS
    // 그래프 정점을 이분했을때 두개의 집합으로 나누자 1번집합과 -1번집합
    // visited 0: 방문하지않음, 1: 1번집합에 속함, -1: -1번집합에 속함
    // BFS탐색을 통해 인접한 접점은 현재 집합과 다른 집합에 속해야한다.
    // 만약 현재 노드의 접점과 인접한 접점이 같은 집합에 속한다면, 이분그래프로 나타낼 수 없다.
    // 간선 연결없는 접점이 존재할 수 있으므로 모든 접점을 BFS탐색 진행한다.
    for i in 1...V {
        if visited[i] != 0 { continue }
        var needVisit = [i]
        visited[i] = 1
        var idx = 0
        while idx < needVisit.count {
            let node = needVisit[idx]
            let color = visited[node] == 1 ? -1 : 1
            if graph[node] == nil { break }
            for j in graph[node]! {
                if visited[j] != 0 {
                    if visited[node] == visited[j] {
                        isBinaryGraph = false
                        break
                    }
                } else {
                    visited[j] = color
                    needVisit.append(j)
                }
            }
            if !isBinaryGraph { break }
            idx += 1
        }
    }
    if isBinaryGraph {
        print("YES")
    } else {
        print("NO")
    }
}