Chapter6 - 너비우선탐색

너비 우선 탐색 - 그래프를 대상으로 하는 탐색 알고리즘

질문 유형 1 : 정점 A에서 정점 B로 가는 경로가 존재하는가?

질문 유형 2 : 정점 A에서 정점 B로 가는 최단 경로는 무엇인가?

위의 두 질문에 대한 답을 얻기 좋은 알고리즘.

망고 판매상 찾기 - 질문 유형 1

  1. 찾아볼 친구 목록 만들기
  2. 목록의 각 사람이 판매상인지 아닌지 확인해보기
  3. 없다면 목록에 각 사람의 친구들도 추가하기
  4. 2번 3번 반복

가장 가까운 망고 판매상 찾기 - 질문 유형 2

  1. 가까움을 정의하기 (ex - 페이스북 친구 = 1촌, 친구의 친구 = 2촌)
  2. 가장 가까운 사람부터 탐색하기.

목록에 추가한 순서대로 찾을때만 가능한 알고리즘 –> 순서가 중요하다.

이 순서를 보장하기 위해 큐를 사용한다.

  • 선입 선출(FIFO)
  • 삽입(Push)와 제거(Pop) 연산

ex)

  1. 버스 정류장의 줄
  2. 대기표 번호 제도(은행, 영화관 등)
  3. 놀이공원 대기줄

그래프

  • 정점과 간선의 조합
  • 방향 그래프(관계에 방향성이 있는 그래프, 방향성은 –> 로 표현)
  • 무방향 그래프(관계에 방향성이 없는 그래프)
  • 방향 그래프를 표현하는 자료구조 –> 해시 테이블

ex) 여러분 –> 밥, 클레어, 앨리스

var graph: [String: [String]] = ["you": ["밥", "클레어", "앨리스"], "bob": ["아누지", "페기
"]]
  • 삽입 순서는 중요하지 않다.
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []

graph["anuj"] = []
graph["claire"] = ["thom", "jonny"]

위의 두 코드는 차이가 없다. Dictionary는 순서를 가지지 않기 때문.

망고 판매상 찾기 알고리즘 구현

  1. 확인할 사람의 명단을 넣을 큐 준비
  2. 큐에서 한 사람을 꺼낸다.
  3. 이 사람이 망고 판매상인지 확인한다.
  4. 맞으면 작업 완료.
  5. 틀리면 그 사람의 이웃을 모두 큐에 추가한다.
  6. 1 ~ 4 반복
  7. 만약 큐가 비어있으면 네트워크에는 망고 판매상이 없다.

큐 제작

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(사람의 수 + 간선의 수)

정리

  1. 너비 우선 탐색은 A에서 B로 가는 경로가 있는지 알려준다. 경로가 존재한다면 최단 경로도 찾아준다.
  2. 방향 그래프는 관계를 나타내는 화살표를 가진다.
  3. 무방향 그래프는 화살표가 없고 둘 간의 상호 관계를 나타낸다.
  4. 큐는 선입선출, 스택은 후입선출
  5. 최단 경로를 구하기 위해 순서가 중요하기 때문에 큐를 이용.
  6. 확인 한 후에는 다시 접근하지 못하도록 해야 무한루프에 빠지지 않는다.
comments powered by Disqus