1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 벨만-포드 알고리즘 특정 출발 노드에서 다른 모든 노드까지의 최단경로 검색 음수 가중치 존재 음수 싸이클 존재 여부 판단 2023.03.20 - [Algorithm/Graph] - [11657번] 타임머신 (그래프, 최단거리, 벨만 포드 알고리즘) 수행과정 모든 에지와 관련된 정보를 가져와 다음 조건에 따라 거리 리스트의 값 업데이트 출발 노드가 방문한 적이 없는 노드(출발 노드 거리 == INF) 일 때 업데이트 X 출발 노드의 거리 리스트 값 + 에지 가..

다익스트라 벨만-포드 플로이드-워셜 시작 노드 (시작점) O O X (모든 노드) 음수 간선 X O O 시간 복잡도 O(ElogV) O(EV) O(V³) 1. 다익스트라 출발 노드와 모든 노드 간의 최단 거리 탐색 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 시간복잡도 : O(ElogV) 문제 유형 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택 노드를 돌아가면서, 더 거리가 나오면 값 갱신하여 저장 더보기 2023.03.15 - [Algorithm/그래프] - [1753번] 최단경로 구하기 (다익스트라, 우선순위큐, 힙) 2023.03.15 - [Algorithm..

11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만 포드 최단 거리를 구하는 알고리즘 음수간선 OK 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 O(VE) 기출 음수사이클이 있는 지 체크하는 문제 → 시간여행, 과거, 웜홀 음수간선, 시작점이 있고 최단거리 구하는 문제 과정 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화 모든 에지를 확인해 정답 리스트 업데이트 음수 사이클 유무 확인 : 모든 에지를 한 번씩 다시 사용해 업데..