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

DFS 와 BFS 에 대한 글은 아래 글을 참고한다.

2020/03/29 - [Algorithm] - 그래프 BFS, DFS 알고리즘 (with Python3)

그래프 BFS, DFS 알고리즘 (with Python3)

 

1. 미로찾기 알고리즘

DFS, BFS 알고리즘을 이용해서 미로찾기 알고리즘을 구현할 수 있다.

 

문제 풀이의 핵심은 2가지이다.

1. 미로 찾기 문제를 풀때는 미로를 모형화하여 그래프로 나타내는 것.
2. 자료구조(Stack 또는 Queue)에 노드(Node)와 비용(Cost) 을 같이 담는 것
   • 노드(Node): 길(경로)
   • 비용(Cost): 거리

그림1. 미로찾기

1.1. 그래프 만들기

파이썬의 딕셔너리(Dictionary) 를 이용하여 그래프를 만든다.

      

      

      

    
    

      <python />
    
# -*- coding: utf-8 -*-

import unittest


class Exam17(unittest.TestCase):

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

# ...

 

1.2. DFS

깊이 우선 탐색으로 스택(Stack)을 이용하여 문제를 풀이한다.

      

      

      

    
    

      <python />
    
# -*- coding: utf-8 -*-

import unittest

# ...

def dfs(graph, start, end):
    """DFS 를 이용하여 미로 찾기 알고리즘을 구현한다.

    :param graph: 미로 그래프
    :param start: 출발 지점(노드)
    :param end: 도작 지점(노드)
    :return: 최소 이동 거리
    """
    stack = [(start, 0)]  # idx 0: 노드, idx 1: 이동 거리
    visit = {start, }  # 방문한 노드 저장 공간

    while stack:
        node, distance = stack.pop()

        new_distance = distance + 1
        for near_node in graph[node]:
            # 방문한 적 없는 노드인 경우
            if near_node not in visit:
                print("{} Node 방문".format(near_node))

                # 도착 지점에 도착한 경우 총 이동거리를 반환
                if near_node == end:
                    return new_distance

                visit.add(near_node)  # 방문
                stack.append((near_node, new_distance))  # 이동 거리를 1 증가 시킨다.

    return -1  # 도착 지점이 막힌 경우(없는 경우)


class Exam17(unittest.TestCase):

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

    # ...

    def test_dfs(self):
        self.assertEqual(10, dfs(self.graph, "A", "M"))
        self.assertEqual(-1, bfs(self.graph, "A", "Z"))  # Z 는 없는 노드


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

 

1.3. BFS

너비 우선 탐색으로 큐(Queue)를 이용하여 문제를 풀이한다.

      

      

      

    
    

      <python />
    
# -*- coding: utf-8 -*-

import unittest


def bfs(graph, start, end):
    """BFS 를 이용하여 미로 찾기 알고리즘을 구현한다.

    :param graph: 미로 그래프
    :param start: 출발 지점(노드)
    :param end: 도작 지점(노드)
    :return: 최소 이동 거리
    """
    queue = [(start, 0)]  # idx 0: 노드, idx 1: 이동 거리
    visit = {start, }  # 방문한 노드 저장 공간

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

        new_distance = distance + 1
        for near_node in graph[node]:
            # 방문한 적 없는 노드인 경우
            if near_node not in visit:
                print("{} Node 방문".format(near_node))

                # 도착 지점에 도착한 경우 총 이동거리를 반환
                if near_node == end:
                    return new_distance

                visit.add(near_node)  # 방문
                queue.append((near_node, new_distance))  # 이동 거리를 1 증가 시킨다.

    return -1  # 도착 지점이 막힌 경우(없는 경우)

# ...

class Exam17(unittest.TestCase):

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

    def test_bfs(self):
        self.assertEqual(10, bfs(self.graph, "A", "M"))
        self.assertEqual(-1, bfs(self.graph, "A", "Z"))  # Z 는 없는 노드

    # ...


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

 

2. Reference

• https://thebook.io/006935/part05/ch16/01-01/