참조

1️⃣ 노드와 간선 구현하기

노드

public class Node<T>: Equatable where T: Equatable, T: Hashable {
  public let value: T
  public var edges: [Edge<T>]
  public var visited = false
  
  init(value: T) {
    self.value = value
  }
  
  public func insertEdgeTo(_ node: Node<T>) {
    let edge = Edge<T>(from: self, to: node)
    self.edges.append(edge)
  }
}

간선

public class Edge<T>: Equatable where T: Equatable, T: Hashable {
  public weak var source: Node<T>?
  public let destination: Node<T>
  
  init(from source: Node<T>, to destination: Node<T>) {
    self.source? = source
    self.destination = destination
  }
}

2️⃣ BFS로 그래프 탐색하기 (with 예제)

아래 번호로 매긴 주석 부분만 응용하면 BFS 문제들에 적용할 수 있다.

  1. 원하는 값 2~N까지의 최소 루트를 구하는 것, i번째 인덱스에 (i+1)번 노드 까지의 최소 루트를 저장하는 배열을 선언함.
  2. Node 방문 시 처리 구간 ‘다음 방문할 노드까지의 최소 거리’ 에 ‘현재 노드를 오는 데까지의 루트’ + ‘다음 방문할 노드의 번호’를 할당
func practiceBFS(n: Int, edges: [(Int, Int)]) {
  // Node, Edge setup
  let nodes = (0..<n).map { Node<Int>(value: $0 + 1) }	// 1~n 값의 value를 가진 노드 n개 생성
  for (from, to) in edges {
    nodes[from - 1].insertEdgeTo(nodes[to - 1])
  }
  
  // 1. BFS로 찾고자 하는 하는 결과
  var shortest = Array(repeating: [1], count: n)
  
  var queue = Queue<Node<Int>>()
  queue.enqueue(nodes[0])
  nodes[0].visited = true
  
  while let node = queue.dequeue() {
    for edge in node.edges {
      let dest = edge.destination
      guard dest.visited == false else { continue }
      queue.enqueue(dest)
      dest.visited = true
      // 2. Node 방문 시 처리해야 하는 구간
      shortest[dest.value - 1] = shortest[node.value - 1] + [dest.value]
    }
  }
  print(shortest)
}

practiceBFS(n: 6, edges: [(1,5), (2,4), (2,5), (3,2), (3,6), (4,2), (4,5), (5,3), (5,6)])
// print "[[1], [1, 5, 3, 2], [1, 5, 3], [1, 5, 3, 2, 4], [1, 5], [1, 5, 6]]"

~ 더 쓸 예정

마지막 수정 날짜: 21.08.05