1. 벨만 포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다. 다익스트라 알고리즘과 달리 매 반복마다 모든 간선을 확인한다. 시간복잡도가 느리다. -> O(VE) 2. 동작 원리 시작점에서 한 정점 x까지의 최단 경로를 구하다고 하면, x를 제외한 모든 노드(V-1)가 시작점과 x 사이의 최단 경로를 구성한다. 모든 정점으로 가는 최단 경로 갱신 과정을 V-1번 반복하면 된다. 음수사이클이 있는지 알아보려면 1번 더 돌려서 최단 거리가 갱신되는지 확인하기 3. 코드 #define INF 987654321 typedef pair P; long long dist[510]; //각 도시의 거리 계산 long long 필수 vec..
C++
1. DFS, BFS란? 그래프 탐색: 하나의 정점으로부터 시작해서 차례대로 모든 정점을 한 번씩 방문하는 것 DFS와 BFS는 그래프 탐색의 일종 2. 동작 방식 DFS: 깊이우선탐색 stack이나 재귀함수를 이용함. 루트 노드에서 시작해서 해당 노드의 자식 노드를 먼저 탐색 이동할 때마다 가중치가 있거나 이동 과정에서 제약이 있는 경우 BFS: 너비우선탐색 queue를 이용함. 루트 노드에서 시작해서 해당 노드의 인접 노드를 우선적으로 탐색 단순 최단 경로를 찾는 문제 3. 코드 //1차원 DFS vector adj[1010]; bool visited[1010]; //dfs방문 void dfs(int now) { Dvisited[now] = true; printf("%d ", now); for (in..
