알고리즘

1. DFS 알고리즘.

BFS에 있던 큐(Queue) 대신에 스택(stack)으로 자료구조를 대체하기만 하면 쉽게 구현하실 수 있다.

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

def dfs(graph, start_node):
# 항상 두개의 리스트를 별도로 관리해주는 것.
    need_visited, visited = list(), list()
# 시작 노드를 시정.
    need_visited.append(start_node)
# 만약 방문이 필요한 노드가 있다면,
    while need_visited:
			# 그중에서 가장 마지막 데이터를 추출.
        node = need_visited.pop()
			# 만약 그 노드가 방문한 목록에 없다면
        if node not in visited:
			# 방문한 목록에 추가.
            visited.append(node)
			# 그 노드에 연결된 노드
            need_visited.extend(graph[node])

    return visited

dfs(graph, 'A')

BFS 알고리즘.

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

BFS 구현 코드.

def bfs(graph, start_node):
    need_visited, visited = [],[]
    need_visited.append(start_node)

    while need_visited:
        node = need_visited[0]
        del need_visited[0]

        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])
    return visited

bfs(graph, 'A')

A* 알고리즘.

class Node:
    def __init__(self, data, hval, level):
        self.data = data
        self.hval = hval
        self.level = level

class Puzzle:
    def __init__(self, start):
        self.start = start

    def h(self, puzzle, goal):
        cnt = 0
        for i in range(3):
            for j in range(3):
                if puzzle[i][j] != goal[i][j]:
                    cnt += 1

        return cnt

    def f(self, puzzle, goal):
        return puzzle.level + self.h(puzzle.data, goal)

    def astar(self, puzzle):
        visit = []
        queue = []
        goal = [['1', '2', '3'], ['8', '0', '4'], ['7', '6', '5']]
        oper = ['up', 'down', 'right', 'left']
        start = Node(data=puzzle, hval=self.h(puzzle=puzzle, goal=goal), level=0)
        queue.append(start)

        while queue is not None:
            current = queue.pop(0)
            if(self.h(current.data, goal)==0):
                return visit
            else:
                visit.append(current.data)
                x, y = checkZero(current.data)

                for op in oper:
                    next = movePuzzle(copy.deepcopy(current.data), x, y, op)

                    if next not in visit and next is not None:
                        queue.append(Node(next, self.h(next, goal), current.level + 1))
                queue.sort(key=lambda x:self.f(x,goal), reverse=False)
        return -1