참조
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 문제들에 적용할 수 있다.
- 원하는 값 2~N까지의 최소 루트를 구하는 것, i번째 인덱스에 (i+1)번 노드 까지의 최소 루트를 저장하는 배열을 선언함.
- 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