문제https://www.acmicpc.net/problem/11779시간 제한메모리 제한solved.ac 티어1초256MB골드 3풀이 이번 문제는 최단경로 문제이면서, 동시에 최단경로도 찾아야 하는 문제이다. 정점의 개수가 1천개밖에 되지 않기 때문에 플로이드 워셜, 다익스트라 모두 가능한 문제일 것이다. 아직 플로이드 워셜 최단경로 역추적을 공부하지 않아, 다익스트라 역추적을 이용해 풀어보았다. 조만간 플로이드 워셜 역추적도 공부해서 풀어보도록 하겠다. 다익스트라 알고리즘에서 최단경로를 역추적하는 방법은 경로를 저장하는 배열을 하나 더 만든다. 각 배열의 인덱스는 정점 번호에 맞추고, 각 배열의 값에는 해당 정점에 오기 전에, 어느 정점을 거쳤는지를 저장한다. 코드로 설명을 하면, prev라는 배열..
문제https://www.acmicpc.net/problem/28707시간 제한메모리 제한solved.ac 티어1초1024MB골드 1풀이 가지고 있는 연산으로 배열을 오름차순으로 정렬시킬 수 있는지, 또한 최소비용이 얼마인지를 알아내는 문제이다. "최소비용"을 구해야 하는 문제이다. 이 문제를 보고 들었던 방법은 매우 많다. 처음에는 백트래킹, BFS를 떠올렸고, BFS를 쓰던 중, 다익스트라로 처리를 할 수 있을 것 같았다. 입력의 제한을 잘 보면 배열의 길이와 연산의 개수가 그리 크지 않다는 점을 알 수 있다. 그래서 배열을 몇번을 복사하던 그리 큰 시간이 들지 않을 것이라 판단했다. 또한 방문체크와 비용을 체크하기 위해선 배열을 만드는 것이 일반적이지만, 어떤 배열이 나올지 알 수 없기 때문에 u..
문제https://www.acmicpc.net/problem/5972시간 제한메모리 제한solved.ac 티어1초MB골드 5풀이 이 문제도 밀려있던 문제이다. 전형적인 최단거리 문제이다. 문제에서 사람 헷갈리라고 가는 길의 길이는 고려하지 않는다고 하지만, 간선 가중치를 여물의 양으로 따져야 하기에 결국은 최단거리 문제로 귀결된다. 우리가 잘 아는 다익스트라를 사용하도록 하자. 잘 쓰던 C++ 대신 자바를 쓴 이유는 당시에 컴퓨터에 깔려있는건 자바밖에 없었다 허허... 그래서 구현과 제출에 정말 애를 먹었던 기억이 있다.코드import java.util.*;import java.io.*;class Pair implements Comparable { public int destination, dist..
문제 시간 제한메모리 제한solved.ac 티어0.5초128MB골드 5풀이 문제 제목이 "최소비용 구하기" 이길래 (왜인지 모르겠지만) 순간적으로 MST 문제인줄 알았다. 하지만 문제를 조금만 읽어보니 최단경로 문제임을 알 수 있었고, 간선 가중치가 모두 음수가 아니기 때문에 다익스트라로 처리하면 끝나는 문제이다.코드#include #define endl '\n'using namespace std;using pii = pair;int n, m, qst, qed;vector> graph;void input() { int st, ed, dist; cin >> n >> m; graph.resize(n + 1); for(int i = 0; i > st >> ed >> dist; graph[st].push_ba..
