탐색 알고리즘 BFS 응용하기 (친밀도 구하기)

BFS 에 대한 개념은 아래 글을 참고한다.
2020/03/29 - [Algorithm] - 그래프 BFS, DFS 알고리즘 (with Python3)

 

탐색 알고리즘 BFS 응용

모든 노드를 탐색(방문)하면서 노드(Node)간의 비용(Cost)을 같이 구한다.

 

문제

사람들간의 친밀도를 구한다.

• 사람: 노드(Node)
• 친밀도: 비용(Cost)

 

예를들어, 사람과 사람 사이의 친밀도를 1 이라 한다. A ~ M 까지 사람이 있을때, A를 기준으로 각각의 사람들과의 친밀도를 구한다.

• A 와 B는 친밀도가 1이다.
• B 와 D는 친밀도가 1이다.
• A와 D는 친밀도가 2이다.
• ...

예시 - 친밀도 구하기

Coding - Python3

본 글에서는 파이썬을 이용하여 문제를 풀이한다. 

 

BFS 알고리즘으로 노드를 탐색하는것은 동일하다. 단, 큐(Queue)에 노드(Node)만 담는 것이 아니라, 비용(Cost)도 같이 담는다.

2개의 값을 담아야 하기 때문에 리스트(List) 또는 집합(Set) 또는 딕셔너리(Dictionary)를 이용한다.

 

아래 코드에서는 집합(Set)을 큐(Queue)에 담는다.

# -*- coding: utf-8 -*-

import unittest


def bfs(graph, start):
    """BFS 를 이용하여 각 노드들의 비용을 구한다."""
    result = {start: 0}

    queue = [(start, 0)]  # idx 0: 노드(Node), idx 1: 비용(Cost)
    visit = [start]

    while queue:
        node, cost = queue.pop(0)

        cost += 1

        near_nodes = graph[node]
        for near_node in near_nodes:
            if near_node not in visit:
                visit.append(near_node)  # 방문 표시
                queue.append((near_node, cost))  # 근접한 노드 정보(노드, 비용) 추가
                result[near_node] = cost  # 결과 값 저장
    return result


class Exam16(unittest.TestCase):

    @classmethod
    def setUp(cls):
        cls.graph = {
            "A": ["B"],
            "B": ["A", "C", "D"],
            "C": ["B", "E", "F"],
            "D": ["B", "G", "H"],
            "E": ["C"],
            "F": ["C", "I"],
            "G": ["D"],
            "H": ["D", "J", "K"],
            "I": ["F", "L"],
            "J": ["H", "M"],
            "K": ["H"],
            "L": ["I"],
            "M": ["J"],
        }

    def test_bfs_a(self):
        self.assertEqual(
            {"A": 0, "B": 1, "C": 2, "D": 2, "E": 3, "F": 3, "G": 3, "H": 3, "I": 4, "J": 4, "K": 4, "L": 5, "M": 5},
            bfs(self.graph, "A")
        )

    def test_bfs_b(self):
        self.assertEqual(
            {"A": 1, "B": 0, "C": 1, "D": 1, "E": 2, "F": 2, "G": 2, "H": 2, "I": 3, "J": 3, "K": 3, "L": 4, "M": 4},
            bfs(self.graph, "B")
        )

    def test_bfs_c(self):
        self.assertEqual(
            {"A": 2, "B": 1, "C": 0, "D": 2, "E": 1, "F": 1, "G": 3, "H": 3, "I": 2, "J": 4, "K": 4, "L": 3, "M": 5},
            bfs(self.graph, "C")
        )


if __name__ == "__main__":
    unittest.main()

 

비슷한 문제로 "미로 찾기" 알고리즘도 구현이 가능하다.

2020/04/01 - [Algorithm] - 미로 찾기 알고리즘 BFS, DFS (with Python3)

미로 찾기 알고리즘 BFS, DFS (with Python3)

Reference

• https://thebook.io/006935/part04/ch15/06-01/