문제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..
문제https://www.acmicpc.net/problem/14938시간 제한메모리 제한solved.ac 티어1초128MB골드 4풀이 이 문제 역시 최단경로 문제이다. 다만, 특정 정점을 시작점으로 잡는 것이 아니라 임의의 정점에서 시작했을 때, 수색 범위 내에 있는 아이템의 개수의 최댓값을 구하는 문제이다. 정점의 개수도 그렇고 간선의 개수도 모두 100 이하이기 때문에 모든 정점에서 다익스트라를 돌려도 되겠으나, 정점의 개수가 적기 때문에 플로이드워셜로 한번에 최단 거리를 구한 후, 각 정점에 대해 순회하며 최댓값을 구했다.코드#include #define endl '\n'using namespace std;vector> graph;vector item;int n, m;void input() { i..
문제 시간 제한메모리 제한solved.ac 티어2초192MB골드 3풀이 이 문제 유형은 예전부터 도전해보고 싶은 유형이었다. 단순히 그래프를 탐색하여 최단경로를 찾는 것이 아닌, 벽을 부수거나 뛰어넘는 등의 지나갈수 없는 길을 조건적으로 지나가는 문제유형은 생각해야하는 것이 정말 많기 때문이다. 사실 전에 의도치 않게 이런 류의 문제의 풀이 일부를 지인에게 스포당했다. 같이 랜덤 실버 디펜스를 하고 있었는데, 이와 비슷한 문제를 시도했다가 실패했고, 지인에게 풀이법을 듣게 되었다. 하지만 그 지인의 말로는 이 풀이를 들었다고 이런 유형의 문제를 다 풀수 있는게 아니라는 말을 듣고 일단은 알겠다고 한 기억이 있다. 스포당한지 어언 5개월 후, 다른 문제인 이 문제를 풀게 되었다. 스포를 당해서 풀이법을 작..
문제 시간 제한메모리 제한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..
