너비 우선 탐색 - 그래프를 대상으로 하는 탐색 알고리즘
질문 유형 1 : 정점 A에서 정점 B로 가는 경로가 존재하는가?
질문 유형 2 : 정점 A에서 정점 B로 가는 최단 경로는 무엇인가?
위의 두 질문에 대한 답을 얻기 좋은 알고리즘.
망고 판매상 찾기 - 질문 유형 1
- 찾아볼 친구 목록 만들기
- 목록의 각 사람이 판매상인지 아닌지 확인해보기
- 없다면 목록에 각 사람의 친구들도 추가하기
- 2번 3번 반복
가장 가까운 망고 판매상 찾기 - 질문 유형 2
- 가까움을 정의하기 (ex - 페이스북 친구 = 1촌, 친구의 친구 = 2촌)
- 가장 가까운 사람부터 탐색하기.
목록에 추가한 순서대로 찾을때만 가능한 알고리즘 –> 순서가 중요하다.
이 순서를 보장하기 위해 큐를 사용한다.
큐
- 선입 선출(FIFO)
- 삽입(Push)와 제거(Pop) 연산
ex)
- 버스 정류장의 줄
- 대기표 번호 제도(은행, 영화관 등)
- 놀이공원 대기줄
그래프
- 정점과 간선의 조합
- 방향 그래프(관계에 방향성이 있는 그래프, 방향성은 –> 로 표현)
- 무방향 그래프(관계에 방향성이 없는 그래프)
- 방향 그래프를 표현하는 자료구조 –> 해시 테이블
ex) 여러분 –> 밥, 클레어, 앨리스
var graph: [String: [String]] = ["you": ["밥", "클레어", "앨리스"], "bob": ["아누지", "페기
"]]
- 삽입 순서는 중요하지 않다.
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["anuj"] = []
graph["claire"] = ["thom", "jonny"]
위의 두 코드는 차이가 없다. Dictionary는 순서를 가지지 않기 때문.
망고 판매상 찾기 알고리즘 구현
- 확인할 사람의 명단을 넣을 큐 준비
- 큐에서 한 사람을 꺼낸다.
- 이 사람이 망고 판매상인지 확인한다.
- 맞으면 작업 완료.
- 틀리면 그 사람의 이웃을 모두 큐에 추가한다.
- 1 ~ 4 반복
- 만약 큐가 비어있으면 네트워크에는 망고 판매상이 없다.
큐 제작
struct Deque<T> {
private var array : [T] = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func push(_ value: T) {
array.append(value)
}
public mutating func pop() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
}
search 함수 제작
func search(name: String) -> Bool {
var queue : Deque = Deque<String>()
for name in graph[name]! {
queue.push(name)
}
var searched : [String] = [String]()
while !queue.isEmpty {
let person = queue.pop()
if !searched.contains(person!) {
if isSeller(name: person!) {
print("\(person ?? "") is a mango seller!!!")
return true
} else {
for name in graph[person!]! {
queue.push(name)
}
searched.append(person!)
}
}
}
return false
}
판매상인지 판별하는 함수 제작
func isSeller(name: String) -> Bool {
return name.last == "m"
}
실행
var graph = [String : [String]]()
graph["you"] = ["alice", "bob", "claire", "thom"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
print("result : \(search(name: "you"))") // true
실행시간 : O(V+E)
-
최소한 O(간선의 개수)
-
큐에 사람을 추가하는 상수시간 O(1), 모든 사람에게 적용하면 O(사람의 수)
-
너비 우선 탐색 : O(사람의 수 + 간선의 수)
정리
- 너비 우선 탐색은 A에서 B로 가는 경로가 있는지 알려준다. 경로가 존재한다면 최단 경로도 찾아준다.
- 방향 그래프는 관계를 나타내는 화살표를 가진다.
- 무방향 그래프는 화살표가 없고 둘 간의 상호 관계를 나타낸다.
- 큐는 선입선출, 스택은 후입선출
- 최단 경로를 구하기 위해 순서가 중요하기 때문에 큐를 이용.
- 확인 한 후에는 다시 접근하지 못하도록 해야 무한루프에 빠지지 않는다.