BOJ 문제풀이/최단경로 (Shortest Path) 썸네일형 리스트형 백준 10159 : 저울 https://www.acmicpc.net/problem/10159 백준 1613 : 역사 문제와 원리가 동일한 플로이드-와샬 알고리즘이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44#include #define MAX 101 #define INF 1000000000 using namespace std; int n, m; int matrix[MAX][MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1; i a >> b.. 더보기 백준 1613 : 역사 https://www.acmicpc.net/problem/1613 얼핏보면 위상정렬 문제같다. 선후관계가 명확하고 그래프가 DAG이기 때문이다.그러나 아예 연결이 안되어 있는 그래프 즉 선후관계가 정해져 있지 않은 그래프를 처리하는게 Topological Sort 로는 애매해보였다. 선후관계를 단방향 그래프로 생각했을 때 전체 그래프의 연결여부를 확인 할 수 있는게 또 하나 있다. 바로, 플로이드-와샬 알고리즘, n=400 이라 충분히 n^3 이 가능해서 생각해보았다. 플로이드 와샬을 썼을때 2차원배열에서 i->j로 갈때 INF가 떴다는 것은 i 에서 j 로 갈 수 없다는 것이다.이때, 만약 j->i 가 INF가 아니라 다른 숫자라면 j->i로는 갈 수 있고 따라서 j 가 i 보다 먼저 일어난 선후관계를.. 더보기 백준 11404 : 플로이드 https://www.acmicpc.net/problem/11404 제목부터 플로이드다플로이드-와샬 알고리즘을 알고있다면 그냥 n^3 한다음에2차원배열을 출력하면 끝. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44#include #define MAX 101 #define INF 1000000000 using namespace std; int matrix[MAX][MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for(int .. 더보기 백준 2660 : 회장뽑기 https://www.acmicpc.net/problem/2660 가장 기본적인 플로이드-와샬 알고리즘 문제이다.다익스트라는 한 점을 기준으로 해서 다른 점들과의 최소비용거리를 계산하지만플로이드-와샬 같은경우 모든 점과 점사이의 경로를 구한다.모든 점과 점사이의 최소비용거리 데이터는 2차원 배열에 저장이 되며 시간복잡도는 n^3 이다. 플로이드-와샬 알고리즘의 경우 동적계획법(DP)의 형태를 가진다.우선 모든 2차원 배열에 저장된 경로를 INF으로 선언하고(자기자신으로 가는경우 i==j 는 0)각 i -> j 로 갈 때 가중치를 저장해준다. ( i -> j 로 가는 경로가 없을때 INF 선언) 현재 정점에서 목적지로 갈때 직접 가는 것보다 다른 점을 거쳐가는 것이 더 빠른 경우를 찾는것 이 핵심이다.간단.. 더보기 백준 9370 : 미확인 도착지 https://www.acmicpc.net/problem/9370 기본적으로 한 지점에서 다른 지점으로 가는 최단경로가 필요한데 어떤 두 정점을 방문해야 하거나 한 간선을 들려야 한다면다익스트라 3번으로 최단경로를 구할 수 있다. start >> n1 -- n2 >> end 는 ① (start->n1) + (n1->n2) + (n2->end) 최단경로와 ②(start->n2) + (n2->n1) + (n1->end) 최단경로를 구할 수 있다. s를 기준으로 다익스트라 할 경우 s->end 까지 최소비용을 알 수 있다.그 값이 ① 또는 ② 둘중 하나와 같다면 end 후보지를 만족한다고 볼 수 있다. ※ 그런데, 더 획기적인 방법이 있다!! (시간이 엄청 짧은 사람의 풀이를 보다가 발견하였다.) 만약 가중치.. 더보기 백준 10282 : 해킹 https://www.acmicpc.net/problem/10282 어떤 컴퓨터x 가 동시에 a,b,c 3대의 컴퓨터를 의존한다고 했을 때 그 컴퓨터x 는 a 또는 b, c 에 의해 감염될 수 있다. 근데 이때 a,b,c 중 가장 감염이 빠른 컴퓨터 기준 걸린 시간 + s 만큼 컴퓨터x 가 감염이 되므로 결국 최단경로를 찾는다익스트라 알고리즘이다. 최소 경로를 갱신할 때 만약 이전 dist값이 INF이면 처음 감염된 컴퓨터이므로 count값을 ++ 시켜주는 것으로 감염된컴퓨터의 총 개수를 구할 수 있고 INF가 아닌 컴퓨터들의 dist중 max값이 가장 마지막 컴퓨터가 감염완료된 시점으로볼 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2.. 더보기 백준 10473 : 인간 대포 https://www.acmicpc.net/problem/10473 한 정해진 출발지점에서 특정 도착지점으로 가는 최단 경로이자 각 노드마다 가중치(시간)가 다르므로 다익스트라로구현할 수 있다. 단 간선이 미리 주어져있지는 않아서 n^2 연산을 통해 모든 정점들을 다 연결하고조건에 따라 1. 대포를 타고 이동할 것인지(거리가 30m 이상이면 대포를 타는 것이 낫다.)2. 걸어서 이동할 것인지 계산해 가중치를 설정해주었다. 이 때 대포를 타든 걸어서 가든 정점과 정점을 사이를 이동할때는일직선으로 이동한다고 가정한다(최소시간) 이렇게 각 정점과 연결된 간선에 대한 설정을 마치면 다익스트라로 최단경로를 구할 수 있다.나는 vertex[1]을 시작지점, vertex[2]를 도착지점으로 설정해주고 시작하였다. 그.. 더보기 백준 1238 : 파티 https://www.acmicpc.net/problem/1238 단방향 도로이고 목적지 까지 가는 것 뿐 만 아니라 돌아가는 것 까지 계산해야한다는 것이 특징이다. 파티마을로 부터 각각의 마을로 돌아가는것은 파티마을을 시작지점으로 한 다익스트라 한번으로 모두 구할 수 있다. 문제는 각자의 마을에서 파티마을로 가는 최단경로를 구하는 것이다. 1. 각자의 마을을 기준으로 파티마을까지 다익스트라를 N-1번 해준다. - 처음에 이처럼 풀었는데 216ms 로 AC받긴 했다.- 그러나 역시 N-1 번 다익스트라를 한다는 것은 매우 비효율적이다. 2. 단방향의 경로를 역으로 설정해 파티마을을 기준으로 다익스트라 한다. - 이것이 훨씬 나은 해결방법이다. 이 경우 총 다익스트라 2번으로 각 마을에서의 왕복시간을 모두.. 더보기 이전 1 2 다음