[DFS] 백준 1707번: 이분 그래프(Swift)

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

1707번: 이분 그래프

난이도: 골드 4

사용언어: Swift

카테코리: DFS

풀이과정

1707번 문제의 주제는 이분 그래프이다.

이분 그래프란, 

위 그림과 같이 각 집합의 정점을 두 분류로 나눌 수 있는 그래프가 이분 그래프이다.

1번 예제 같은 경우, 

위와 같이 표현할 수 있기 때문에, 이분 그래프라고 할 수 있다. 하지만, 2번 예제 같은 경우

2와 4가 한 분류로 묶이기 때문에 이분 그래프가 될 수 없다.

위 처럼, 색으로 나눠볼 수 있기 때문에 문제에서 

0, 1로 두 분류로 나눴으며, 탐색하지 않은 노드는 -1로 표시하였다.

code

struct Queue<T> {
  var memory = [T]()
  var index = 0
  
  var isEmpty: Bool {
    memory.count < index + 1
  }
  
  mutating func inQueue(element: T) {
    memory.append(element)
  }
  
  mutating func deQueue() -> T {
    let v = memory[index]
    index += 1
    return v
  }
}

let k = Int(readLine()!)!
var results = [String]()
for _ in 0..<k {
  let ve = readLine()!.split(separator: " ").map { Int($0)! }
  let v = ve[0]
  let e = ve[1]

  var links: [[Int]] = Array(repeating: [], count: v + 1)
  var nodeColors = Array(repeating: -1, count: v + 1)

  for _ in 0..<e {
    let v = readLine()!.split(separator: " ").map { Int($0)! }
    links[v[0]].append(v[1])
    links[v[1]].append(v[0])
  }

  var q = Queue<Int>()
  var result = "YES"
  
  func bfs(start: Int) {
    nodeColors[start] = 0
    q.inQueue(element: start)
    while !q.isEmpty {
      let c = q.deQueue()
      for i in links[c] {
        if nodeColors[i] == -1 {
          nodeColors[i] = nodeColors[c]^1
          q.inQueue(element: i)
        } else if nodeColors[i] == nodeColors[c] {
          result = "NO"
          return
        }
      }
    }
  }
  
  for i in 1...v {
    if nodeColors[i] == -1 {
      bfs(start: i)
      if result == "NO" { break }
    }
  }
  results.append(result)
}

results.forEach {
  print($0)
}