-
[Algorithm] BFS 연습하기Etc./Algorithm 2020. 9. 11. 17:01
안녕하세요 :)
오늘은 알고리즘 중에서 제가 제일 어려워하는 너비 우선 탐색, 간단한 문제를 BFS로 Swift로 풀어볼 거예요.
어느 알고리즘이든 DFS는 어떻게든 풀겠는데 BFS는 어렵더라고요..!
마침 내일이 카카오 코딩 테스트 날이기도 하니까! 알고리즘을 가져왔습니다.
어떤 문제에 BFS를 사용하나요?
BFS는 말 그대로 너비 우선 탐색, 너비를 우선으로 탐색하는 것인데요.
너비 우선 탐색은 최단 거리를 찾아주기 때문에 최단/최소 경로를 탐색할 때 주로 사용됩니다.
보통 큐를 활용해서 많이 구현하기 때문에, 큐를 구조체로 구현할 것입니다.
대략의 구현 방법
우선 BFS에서 처음 시작할 때, 시작 노드를 큐에 삽입해줍니다.
또한, 시작 노드를 방문했다고 체크해줍니다.
그 후로부터는 아래와 같이 작동합니다.
- 큐에서 노드 하나를 꺼냅니다.
- 꺼낸 노드와 연결되어있는 노드 중에서 여태까지 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입해줍니다.
간단한 문제로 BFS 구현해보기
Q. 1부터 시작해서 N개의 노드를 가지는 방향 그래프가 주어지면, 1번 노드로부터 2~N번 노드까지 도달할 수 있는 최단 루트를 구하세요.
위의 문제를 풀면서 BFS를 구현해 볼 것입니다.
제가 임의로 설정한 값은, N = 6이고 edge는 [(1, 5), (2, 4), (2, 5), (3, 2), (3, 6), (4, 2), (4, 5), (5, 3), (5, 6)]입니다.
이렇게 설정하면 아래와 같은 그래프가 나옵니다.
1번에서 출발하여 최단 루트들을 구해볼 겁니다.
Queue 구조체
// 큐 struct Queue<T> { private var list = [T]() var isEmpty: Bool { return self.list.isEmpty } var front: T? { return self.list.first } mutating func enqueue(_ item: T) { self.list.append(item) } mutating func dequeue() -> T? { guard self.isEmpty == false else { return nil } return self.list.removeFirst() } }
우선 Swift에는 내장된 큐가 없기 때문에, 배열을 활용해서 큐 구조체를 만들어주었습니다.
어떤 타입이 들어올지 모르기 때문에 제네릭 타입으로 설정해주었고, 큐에 아이템들을 추가해주는 enqueue와 첫 번째 아이템을 제거하는 dequeue 함수를 작성했습니다.
* mutating
구조체 내부에서 값들을 변경해주기 때문에, 컴파일 에러가 발생하지 않으려면 mutating을 함수 앞에 작성해주어야 한다.
Node 클래스
// 간선 class Node<T> { let value: T var edges = [Edge<T>]() var visited = false init(value: T) { self.value = value } func appendEdgeTo(_ node: Node<T>) { let edge = Edge<T>(from: self, to: node) self.edges.append(edge) } }
그 후에 그래프 사이의 가중치와 방문 여부를 체크하기 위해서 Node 클래스를 작성해주었습니다.
그리고 노드와 연결된 엣지들을 추가시키기 위해서 appendEdgeTo 함수를 작성했습니다.
Edge 클래스
// 그래프 엣지 class Edge<T> { weak var source: Node<T>? let destination: Node<T> init(from source: Node<T>, to destination: Node<T>) { self.source = source self.destination = destination } }
Edge는 해당 Edge와 연결된 도착 Edge를 포함하는 클래스입니다.
출발지와 도착지가 모두 설정되어야 하기 때문에 초기화 작업 때 설정해줍니다.
BFS
func practiceBFS(n: Int, edges: [(Int, Int)]) { let nodes = (0..<n).map({ Node<Int>(value: $0 + 1) }) for (from, to) in edges { nodes[from - 1].appendEdgeTo(nodes[to - 1]) } 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 destination = edge.destination guard destination.visited == false else { continue } queue.enqueue(destination) destination.visited = true shortest[destination.value - 1] = shortest[node.value-1] + [destination.value] } } print(shortest) }
최종적으로 구현된 bfs 함수는 위와 같습니다.
우선 Node와 Edge를 설정합니다.
shortest는 최단 경로로 최종적으로 구해야 하는 값이기 때문에 마지막에 print를 해주었습니다.
큐도 노드 타입으로 설정해주고, 노드의 첫 번째인 루트 노드를 큐에 삽입해주고 방문 여부를 true로 설정해줍니다.
그리고 큐에 노드들이 있을 때, 노드와 연결된 엣지들을 루프를 돕니다.
만약 방문했다면, contine를 활용해서 다음 루프로 넘어갑니다.
방문하지 않은 노드라면 현재 노드에서 도착지인 destination을 큐에 삽입해주고, 방문 여부를 true로 설정해줍니다.
구현
practiceBFS(n: 6, edges: [(1, 5), (2, 4), (2, 5), (3, 2), (3, 6), (4, 2), (4, 5), (5, 3), (5, 6)])
위와 같이 함수를 호출해주면, 아래와 같이 최단 경로들이 출력됩니다.
마무리
오늘은 Swift로 BFS를 구현해봤는데요.
제가 알고리즘을 풀 때 주 언어는 Swift가 아니지만, 스터디 공부도 할 겸 알고리즘 공부도 할 겸 포스팅해봤습니다.
BFS에 대해 개념이 많이 헷갈렸었는데 공부하면서 개념을 확실하게 잡을 수 있게 되어서 정말 좋았습니다 :)
오늘도 포스팅 봐주셔서 감사합니다! 🤗
'Etc. > Algorithm' 카테고리의 다른 글
[Algorithm] 프로그래머스 Lv2 주식가격 (42584) (0) 2021.02.23 [Algorithm] 프로그래머스 Lv2 기능개발 (42586) (0) 2021.02.19 [Algorithm] 프로그래머스 Lv2 조이스틱 (42860) (0) 2021.02.19 [Algorithm] 프로그래머스 Lv2 프린터 (42587) (0) 2021.02.17 [Algorithm] 알고리즘 풀이 작성 시작! (2) 2021.02.17