1260 DFS와 BFS / DFS, BFS
정답from collections import dequedef DFS(graph, start, visited, dfs_ans): visited[start] = True dfs_ans.append(start) for i in graph[start]: if visited[i] is False: DFS(graph, i, visited, dfs_ans)def BFS(graph, start, visited, bfs_ans): queue = deque() queue.append(start) visited[start] = True while queue: v = queue.popleft() bfs_ans.append(v) ..
11724 연결 요소의 개수 / DFS, BFS
인접리스트 만들기n, m = map(int, input().split()) # 정점, 간선의 개수con = []for i in range(m): a, b = map(int, input().split()) con.append((a,b))# 그래프 세팅, 이차원 리스트로 만들기graph = []for i in range(0, n + 1): graph.append([])for a, b in con: graph[a].append(b) graph[b].append(a) 정답def DFS(graph, start, visited): visited[start]= True # print(start, end=' ') for i in graph[start]: if vi..
DFS와 BFS
그래프그래프 : 복잡하게 연결된 자료 객체 사이의 관계를 효율적으로 표현한 것객체 : 정점관계 : 간선 (= 객체간의 관계)그래프 : 접점과 간선의 집합으로 구성됨 -> A와 B를 연결하는 간선 (A, B)인접 : 간선으로 연결된 두 정점을 인접해 있다고 함차수 : 정점에 연결된 간선의 수경로 : 간선을 따라 갈 수 있는 길을 순서대로 나열한 것연결그래프 : 모든 정점사이에 경로가 존재하는 그래프트리 : 사이클을 가지지 않는 연결 그래프 그래프의 표현 : 인접리스트를 이용한 표현인접리스트 : 각 정점이 인접한 정점 리스트를 갖도록 하는 것 -> [[], [2, 5], [1, 5, 4, 3], [4, 2], [3, 6, 5, 2], [2, 1, 4], [4]]그래프 순회 : 하나의 정점에서 시작하여 그래프..
