BFS와 최단 경로 BFS는 최단거리와 관련있다. 왤까? BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다. bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다. 그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다. 흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;; 예시를 보자. 시작점 A에서 F까지의 최단경로를 알아..

알고리즘 아래와 같이 그래프의 연결 상태가 주어진다면, 인접 리스트와 인접 행렬 두 가지 방식으로 관계를 정의할 수 있다. 이 문제에서는 인접 리스트를 사용하여 그래프 관계를 정의하겠다. 1 2 1 3 1 4 2 4 3 4 [인접리스트를 활용한 그래프 표현] 1. 간선의 개수 만큼 정점의 관계들이 입력 되니까 간선의 수 만큼 for문을 반복. 2. 두 정점을 입력 받아서 연결관계를 표현하기 위해 서로의 리스트에 저장. 이때 정점의 정보는 1 ~ n까지의 숫자로 나타나므로, graph의 크기를 n+1만큼 해주어야 한다. (range 함수는 n-1까지의 수를 반환하니까) # 그래프 초기화 graph = [[] for _ in range(n+1)] # 간선의 개수가 m일 때 for _ in range(m) :..

dfs : 최대한 깊게 방문하지 않은 노드들에 쭉 방문하다가, 더이상 진행할 수 있는 인접정점이 없으면 되돌아감 - 재귀 bfs : 한 노드에서 인접노드까지 방문한 적이 없는 모든 노드를 queue에 삽입. que는 FIFO 방식이라서 순차적인 구현 가능 popleft로 앞에거 빼주면 됨 ㅇㅇ dfs 구현 from collections import deque r,c = map(int, input().split()) pasture = [list(input()) for _ in range(r)] visit = [[0]*c for _ in range(r)] d = [(0,1),(0,-1),(1,0),(-1,0)] cnt = 0 def dfs(x, y) : visit[x][y] = 1 for dx, dy in ..

트리 트리란? 회사의 조직도, 가계도와 같이 나무처럼 뻗어나가는 모양의 사이클이 없는 그래프다. 노드 간선 루트 노드: 트리의 맨 꼭대기 부모 노드/자식 노드 리프 노드: 자식이 없는 노드 차수와 깊이 그리고 높이 차수: 특정 노드의 자식 수 깊이: 특정노드로부터 루트노드와 떨어져있는 정도 높이: max깊이 + 1 이진트리 트리의 자식을 2개로 한정하면, 이진트리 배열로 나타내기 좋다. 부모는 i, 왼쪽 자식은 i2, 오른쪽 자식은 i2+1 만약 모든 자식이 꽉 차있지 않다면 배열도 같이 비워줘야한다. 이진트리는 한번 알면 여러모로 편하다.. 자식이 2개로 제한되어 있기 때문에 구현도 좋다… 그러니 확실하게 알아둘 것! 트리의 순회 트리를 탐색하는 순회 방법은 3 가지가 있다. 전위 순회(왼>뿌>오) 중..