Algorithms/Shortest path

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. Preview 시간 복잡도: O(NlogM*N) N : 현재 노드와 연결된 간선 수 (최대 N) logM : 간선 heap 추출 N : N번의 다익스트라 공간 복잡도: O(M) 참고 : - 유형: 다익스트라 2. 초기 접근 방법 'i에서 X까지의 소요시간' 과 'X에서 i까지의 소요시간' 을 구한 뒤 가장 오래 걸리는 소요시간을 구하면 된다. # x에서 i까지..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 1. Preview 시간 복잡도: O(3(V+E)) 공간 복잡도: O(N) 참고 https://frog-in-well.tistory.com/68 https://ddingmin00.tistory.com/entry/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-9370%EB%B2%88-%EB%AF%B8%ED%99%95%EC%9D%B8-%EB%8F%84%EC%B..

[초기 접근 방법] 1. 랜덤 지점에서, 랜덤 지점까지 갈 수 있는지를 체크해야 한다. 2. 플로이드 알고리즘으로 minDis[][] = '최소거리', 모든 노드에서의 최소 거리를 구한다. 3. minDis[s][e] 를 출력한다. [생각] 문제는 단방향 길을 양방향으로 고치는 것이다. 따라서 존재하는 길을 '0', 단방향이면서 존재하지 않는 길을 '1'로 설정해 최단경로를 찾으면 된다. 추가로 minDis를 초기화 할 때, 주어지지 않은 길은 FIX 값으로 초기화하고 해당 길은 탐색하지 않도록 하자 [코드] # 풀이 시간 : 47분 # 시간복잡도 : O(N^3) # 공간복잡도 : O(N^2) # 참고 : - import sys input = sys.stdin.readline FIX = 10000 # ..

[초기 접근 방법] 모든 노드 쌍에 대한 최단 거리 루트에서, 첫번째 방문 지역을 알아야 된다. 따라서 플로이드 알고리즘을 사용한다. 이 때, graph[i][j] 값이 갱신될 때의 k를 result[i][j] = k 로 저장한다. → result[i][j] : i에서 j까지 이동하는데, 가장 먼저 들려야 하는 지점 [생각] 위 접근 방법에서 잘못된 점을 디버깅 하면서 발견했다. k 값이라도 순수하게 가장 먼저 들려야 하는 지점이 아니라, i에서 k까지 가는데 가장 먼저 들려야 하는 지점이 있을지도 모른다는 사실을 간과했다. 이러한 사고를 코드로 반영하게 되면, 다음과 같다. # 초기 코드 result[i][j] = k # 수정 코드 result[i][j] = result[i][k] [코드] # 풀이 시..

[초기 접근 방법] - 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 체크 → 음의 사이클 유무 파악 → 벨만포드 알고리즘 사용 [생각] 1. '타임머신' 문제 이후 오랜만에 풀었던 벨만포드 알고리즘 문제 2. 어떻게 접근하는지, 풀어야하는지 잊어서 여러 블로그를 참고해서 이해했다. 3. 파이썬에서 float('inf') - int 를 해도 그대로 무한대이다.. 4. 시작 지점과 관계가 없다면, 그저 현재 그래프에서 음의 사이클이 있는지 파악하게 된다. 음.. 일단 타임머신 문제에서 parameter로 1을 넘겼지만, 1 시작 지점과 관계없이 알고리즘이 진행되었다. ( 이 때는, 1 노드 시작을 하려면 "minDis[start] != INF" 를 넣어야 하는지도 인지하지 못했음... ㅎ..

https://www.acmicpc.net/problem/11657 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 [초기 접근 방법] 일단 사이클이 존재하려면 "간선의 개수(E)가 노드의 개수(N) 이상"이어야 한다. 따라서 마지막 N번째 탐색을 할 때 (사이클이 존재하지 않더라도) 최소 거리가 갱신이 된다면, 음의 사이클이 존재한다는 의미이다. [생각] - 벨만포드 알고리즘의 기본 문제 - 어떻게 풀 지 생각이 나지 않는다면, 위의 플로우를 떠올리..