알고리즘/최단경로3

• 

  [백준] 11657번: 타임머신 - java 음수가중치가 있는 문제이므로 다익스트라로는 최단 경로를 갱신할 수 없다. => 다익스트라는 이미 방문한 노드에 대해서는 더 이상 경로탐색을 하지 않기에 (더 탐색하면 양의 가중치를 더 얻게 되므로 당연히 탐색할 필요X) 최단 경로를 판별할 수 없다. 따라서 벨만포드를 사용해서 모든 edge에 대해서 edge relaxation 을 (V-1) 번 수행해준다. 그런데 왜 V-1 만큼일까? V-1 만큼 모든 간선을 탐색하는 것이 확 와닿지가 않았다. 그림으로 이해해보자. 출발점이 A라고 생각해보자. 1번째 방문시, 다음과 같이 갱신이 된다. 사실 A->D 간선이 먼저 갱신된다면 1번째 방문에서 D->C 도 갱신되겠지만, 최악의 경우를 고려했을 때는 아래와 같다. 간선의 순서와 상관없이 A에서 출발하는 간선의 .. 알고리즘/최단경로 2023. 3. 29.

• 

  [백준] 1238번: 파티 - java 아이디어 V = 정점의 갯수 E = 간선의 갯수 T = 목적지 (파티가 열리는 곳) 라고 할 때 다익스트라를 V번 반복하지 않아도 이 문제를 풀 수 있다. 1) T를 출발 노드로 하여 다익스트라 알고리즘을 돌린다. => T에서 출발해서 다른 노드로 가는 최단경로를 모두 구한다. 그럼 이제 임의의 노드 x에서 출발해서 T로 오는 거리만 찾으면 답을 구할 수 있다. 2) x -> T 거리를 구하기 위해선 출발노드 x가 매번 다르기 때문에 다익스트라를 n번 반복해야 한다. 하지만 그래프 간선방향을 거꾸로 뒤집고, (1->3 을 3->1 으로 변경) T 노드를 출발 노드로 하여 다익스트라를 돌리면 x -> T 의 거리를 모두 구할 수 있다. 3) 1, 2 에서 구한 거리를 더해서 가장 큰 값을 찾는다! 이렇게 .. 알고리즘/최단경로 2023. 3. 28.

• 

  [백준] 11404번: 플로이드 - 파이썬(python) 나의 풀이 n = int(input()) m = int(input()) dis = [[int(1e9)] * (n+1) for _ in range(n+1)] for i in range(n+1) : dis[i][i] = 0 # 자기 자신으로 가는 노선은 0 for _ in range(m) : a, b, c = map(int, input().split()) dis[a][b] = min(dis[a][b], c) # a도시에서 b도시로 가는 비용 저장 for k in range(1, n+1) : for i in range(1, n+1) : for j in range(1, n+1) : dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]) for i in range(1, n+1) .. 알고리즘/최단경로 2022. 10. 20.