1. 가중치가 별도로 주어져있다
- No: BFS, DFS로 풀이. but, dfs보다는 bfs를 더 선호. 이유: 보통 bad일경우 dfs, bfs 전부 같지만 일반적인 good 상황에서는 bfs 단계에서 끝나는 경우가 많음.
- DFS
- 일반적으로 표기는 다음과 같이 진행된다.
- 순회 과정(stack 방식 활용)
- A와 연결된 Node는 b와 c
- b와 c 중 선택해서 다음 level 선택
- 또 그다음 level 선택
- 반복
- BFS (Queue 방식 활용)
- 같은 깊이에 해당하는 노드부터 탐색
- A -> B -> C -> D -> E -> G -> F 순으로 가로로 체크
- YES: 다익스트라 알고리즘, 프림 알고리즘, 크루스칼 알고리즘
1. 다익스트라 알고리즘(정점 기반) (OElogv)
- 출발지를 선택하고 distance를 0으로 설정
- 출발지와 연결된 distance를 update
- 현재까지 update된 distance를 보고 가장 좋은 길을 선택
- 이미 선택되서 distance가 update가 되어 있더라도 더 짧은 경로가 있다면 update 해주어야 함.
- 다익스트라를 끝까지 돌린다고 MST가 100프로가 아닐수도 있다.
2. 크루스칼 알고리즘 (ONlogn)
- 가중치가 최소인 간선을 하나씩 선택해 나가는 (간선 기반 알고리즘)
- 사이클이 발생하는 경우는 예외 처리가 필요
3. 프림 알고리즘
- 정점 하나를 선택한 후 정점에 연결된 간선 중 가중치가 가장 작은 간선을 선택해서 나가는 정점 기반 알고리즘
- 정점을 하나씩 선택해 나가기 때문에 사이클을 고려가 된다.
최단경로 알고리즘
1. 하나의 시작 정점에서 끝 정점까지의 최단 경로 구하는 문제 (시작 정점 , 끝 정점 주어짐)
- 다익스트라 알고리즘: 음의 가중치를 허용하지 않음(Greedy로 쉽게 풀림)
- 벨만 - 포드 알고리즘: 음의 가중치를 허용
- 정점 - 1 번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해간다.
- 매 반복마다 모든 간선을 확인해야함.
- 음수 간선이 있어도 최적의 해를 찾을 수 있는 이유: 음수 간선의 순환을 감지할 수 있기 때문
- o(ve)
- 수행과정
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 반복
- 모든 간선 E개를 하나씩 확인
- 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 음수 간선 순환 발생 체크하고 싶으면 반복을 다시 돌려서테이블 갱신되는지 확인된다.(갱신되면 음수 간선 순환 있음)
- .
2. 모든 정점들에 대한 최단 경로
- 플로이드-워샬 알고리즘
- 모든 정점 기준으로 table들 전부 계산
- dp 테이블에 속한다고 볼 수 있음
- 2차원 테이블을 활용 (다익스트라는 list 형식일 가능성이 높다)
- 노드가 N개일때 N 번수행인데 N단계라서 N^3이다.
참고
'Algorithms > 2023 Pro 시험 준비' 카테고리의 다른 글
| 1621 알고스팟 - 백준 (0) | 2023.07.24 |
|---|---|
| 2811 알약 - 백준 (0) | 2023.07.24 |
| 10217 KCM Travel - 백준 (0) | 2023.07.17 |
| 1865 웜홀 - 백준 (0) | 2023.07.17 |
| 2211 내트워크 복구 - 백준 (0) | 2023.07.17 |
