2020/08

    [Python] 백준 1260

    [Python] 백준 1260

    단순히 DFS와 BFS를 구현하여 출력하면 된다. 그래프 구현 graph = [[0]*(N+1) for x in range(N+1)] for i in range(M): temp = list(map(int, input().split(' '))) graph[temp[0]][temp[1]] = 1 graph[temp[1]][temp[0]] = 1 그래프는 2차원 배열로 구현하였다. 두 정점을 연결하는 간선을 1로 바꿔준다. 양방향 그래프이기 때문에 두 번 바꿔주어야 한다. 예를들어 간선이 1과 2를 연결한다면, 2차원 배열은 다음과 같다. DFS 구현 탐색을 시작할 정점을 파라미터로 받아 dfs를 수행하는 함수이며, recursive로 구현하였다. graph에서 연결된 정점을 리스트로 만들고, 리스트에 해당하..

    [Algorithm] 너비 우선 탐색 BFS / 깊이 우선 탐색 DFS

    [Algorithm] 너비 우선 탐색 BFS / 깊이 우선 탐색 DFS

    개인적으로 어려워 하는 알고리즘,, 알고리즘 BFS는 FIFO를 원칙으로 하는 Queue로 구현한다. 탐색을 시작하는 첫 노드(root)를 queue에 넣고 탐색을 시작한다. A. queue에서 노드를 꺼낸다. B. 꺼낸 노드와 연결된 노드 중 방문하지 않은 노드를 방문하고 queue에 넣는다. queue에 노드가 없어질 때 까지 AB반복 구현 def bfs(graph, root): visit = list() queue = [root] #AB반복 while queue: temp = queue.pop(0) if temp not in visit: print(temp) visit.append(temp) queue.extend(graph[temp]) 알고리즘 DFS는 LIFO를 원칙으로 하는 Stack으로 구현..