[초기 접근 방법] 모든 노드 쌍에 대한 최단 거리 루트에서, 첫번째 방문 지역을 알아야 된다. 따라서 플로이드 알고리즘을 사용한다. 이 때, 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. 모든 땅을 고르게 한다. min ~ max 까지 땅의 높이를 고르게 했을 때, 소요 시간을 파악한다. 이전 소요 시간보다 크면 멈추고 출력 (최적화) 2. 시간을 계산한다. if n > k (목표 높이가 높을 때) n의 높이로 설정했을 때, n-k 쌓을 블록이 필요 → 1 elif n < k (목표 높이가 낮을 때) k-n 블록을 제거 → 2 3. B + push < need n 높이로 고르게 만드는 건 불가능 [생각] - 완전 탐색 문제 - 파이썬으로 제출할 때, elif로 조건 처리하게 되면 시간초과가 난다. else 로 256MN 처리를 줄여줘야 통과할 수 있다. [코드] # 풀이 시간 : 30분 # 시간복잡도 : O(256MN) # 공간복잡도 : O(MN) # 참고 : -..

[초기 접근 방법] - 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 체크 → 음의 사이클 유무 파악 → 벨만포드 알고리즘 사용 [생각] 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번째 탐색을 할 때 (사이클이 존재하지 않더라도) 최소 거리가 갱신이 된다면, 음의 사이클이 존재한다는 의미이다. [생각] - 벨만포드 알고리즘의 기본 문제 - 어떻게 풀 지 생각이 나지 않는다면, 위의 플로우를 떠올리..

https://www.acmicpc.net/problem/1277 1277번: 발전소 설치 첫 줄에는 발전소의 수 N(1 ≤ N ≤ 1,000)과 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000)가 주어진다. 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)가 주어진다. 다음 N개의 줄에는 1번 발전소부터 N번 발 www.acmicpc.net [초기 접근 방법] 1. 1번 발전소에서 N번 발전소까지만 가면 된다. 즉, "1"에서 "N"까지의 최소 경로를 구해야 하므로, 다익스트라 알고리즘을 사용한다. 2. 추가 전선의 길이가 최소가 되게끔 이동한다. 이 때, 두 발전소 사이의 전선 길이가 M을 초과해서는 안된다. 2차원 좌표를 그래프로 표현하면 공간 복잡도가 100억이 나오므로 불..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net [초기 접근 방법] 1. 어느 위치에 떨어지는 것이 아이템을 가장 많이 얻을 수 있는가? 2. 모든 노드에서 간선에 대한 수색 범위를 펼쳐서 아이템을 얻는 개수를 구해야 한다. → graph[i]를 중심으로 탐색 범위, 'graph[i][j]