Code/algorithm8 알고리즘 | 탐색 기본, 인접행렬과 인접리스트 인접행렬 자기 자신 : 0 연결 된 엣지 : 1 (또는 1*weight) 연결 안 된 엣지 : Inf (무한대 값으로 0과 구분) # infinite 값을 선언하기 INF = float('inf') # 행렬 그래프로 나타내기 - 가중치 weight 고려해서 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] 도시끼리 연결되었는지 어떻게 확인할까? graph[0][1] >>> 7 (0번과 1번 도시가 연결됨) graph[2][1] >>> inf (2번과 1번 도시가 연결 안 됨) 인접리스트 모든 노드에 연결된 노드에 대한 정보를 차례차례 연결하여 저장 # 연결된 도시만 리스트로 표현 graph = [ [(1, 7), (2, 5)], # --> 0번 도시의 연결 리스트.. 2024. 4. 1. 알고리즘 | 탐색 기본, DFS / BFS 엣지를 따라 모든 노드를 방문하는 것을 그래프 탐색이라고 한다. 대표적으로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있다. Depth First Search (깊이 우선 탐색) 깊이 우선 탐색은 기본적으로 Stack이다. (Last In First Out) 오른쪽 왼쪽 상관은 없음 예제 graph_list = [ [], # 0번 도시(없음) [2, 3, 8], # 1번 도시 [1, 7], # 2번 도시 [1, 4, 5], # 3번 도시 [3, 5], # 4번 도시 [3, 4], # 5번 도시 [7], # 6번 도시 [2, 6, 8], # 7번 도시 [1, 7] # 8번 도시 ] 1번 도시 방문 To do : [2, 3, 8] 2번 도시 방문 To do : [1, 7] -> 1번은 됐고 7번 .. 2024. 4. 1. 이전 1 2 다음
