알고리즘225 BOJ 5719 - 거의 최단 경로 (다익스트라) https://suuntree.tistory.com/120?category=797985참고 https://www.acmicpc.net/problem/5719 참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다. 최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라 1) 다익스트라https://suuntree.tistory.com/120?category=797985참고 https://www.acmicpc.net/problem/5719 참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다. 출발점 s에서 도착점 e로 갈때, 최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라 1) 다익스트라를 적용해서 dist배열을 초기화 한다. 2) 도착점 부터 역방향 인접배열를 사용해서 모든 .. 2020. 1. 27. BOJ 1854 - K번째 최단경로 찾기(다익스트라) https://www.acmicpc.net/problem/1854 다익스트라 알고리즘을 완전 이해해야 풀 수 있었던 문제. 가중치가 항상 양수이므로 다익스트라 사용 한 도시를 여러번 방문할 수 있다. 이 조건을 명시하지 않아서 조금 어색하게 느껴졌던 것 같다. https://cses.fi/problemset/result/312681/ 유사문제 단방향 가중치 그래프가 주어진다. 1번도시에서 출발하여 i번째 도시로 갈 때 k번째 최단 길이를 찾아라. (중복허용 ex) 2번도시로 가는 길이가 1 3 3 5 이고 k==3이면 답은 3이다.) 우선 나이브하게 접근해보면 dist[i] : 1번도시에서 출발하여 i번째 도시로 가는데 길이를 모두 저장. 위 경우, dist[i]는 pq혹은 set으로 구현할 수 있다. .. 2020. 1. 25. BOJ 1162 - 도로포장 (다익스트라) https://www.acmicpc.net/problem/1162 정점의 상태를 잘 정의하고 정의된 정점 간의 간선이 어떻게 이어져있는지를 잘 파악하면 된다. 양방향 가중치 그래프가 주어진다. 연결된 간선에 대해서 최대 k번 가중치를 0으로 만들 수 있을 때, 정점 1에서 정점n으로 가는 최단길이는? u번 정점 전까지 도로포장을 t번했다면 정점을 (u,t)로 정의한다 (정점의 상태가 최대 20개라서 가능) u->v에 대해 (u,t) -> (v,t), (v,t+1) .. t+1 다익스트라로 풀 수 있다. typedef pair P; typedef pair T; const int MAX = 1e4 + 2; const ll INF = 1e18; vector adj[MAX]; ll dist[MAX][21]; i.. 2020. 1. 25. 사이클 검출 ㅁ 양방향 그래프 https://cses.fi/problemset/task/1669 prv배열과 사이클의 끝점, 시작점을 잘 캐치하면 된다. 양방향 그래프가 주어질 때 사이클이 없으면 IMPOSSIBLE출력, 있으면 아무 사이클이나 사이클을 이루는 정점의 크기와 정점번호들 순서대로 출력 const int MAX = 1e5 + 2; int n, m, prv[MAX], st, en; vector adj[MAX]; bool vst[MAX], fin[MAX]; void dfs(int curr, int pr=0) { vst[curr] = true; for (int next : adj[curr]) { if (!vst[next]) { prv[next] = curr; dfs(next,curr); } //다음 정점이 방.. 2020. 1. 23. 이전 1 ··· 22 23 24 25 26 27 28 ··· 57 다음