OILAT

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 그래프 탐색 (Graph Search, DFS & BFS) - 응용 편 2 학습 후기 그래프 탐색할 때 BFS를 사용하여 A에서 B까지 갈 수 있는지와 A에서 다른 경로까지의 최소 이동 횟수도 계산 가능하다. 단, 최소 이동 횟수만 말하는 거지 간선에 가중치가 포함되어 있다면 안된다. 최소 이동 횟수, 최단 시간 키워드가 존재하면 사용해볼 만하다. 1. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.n..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 그래프 탐색 (Graph Search, DFS & BFS) 학습 후기 알고리즘에서 그래프 = 정점(Vertex) + 간선(Edge) 간선: 무방향 / 방향 + 가중치 가 있을 수 있음 정점의 차수(degree): 정점 x의 차수는 정점 x에 연결된 간선의 수 모든 정점의 차수의 합 = 간선의 개수의 2배, 이유는 모든 정점의 차수를 더하면 한 간선이 두 번씩 중복해서 더해지므로 2배가 된다. 그래프를 저장하는 방법 1. 인접 행렬: 2차원 행렬로 이어지는 간선이 있는 곳에 1을 표시한다. 0으로 표시되어있다면 연결되어 있지 않다. 가중치 그래프일 경우 0, 1 대신 가중치로 표시하기도 함. O(V^2) 만큼의 공간이 필요하다..