알고리즘/BOJ 썸네일형 리스트형 11404번 11404번 - 플로이드 플로이드 워셜 기본 문제. 단, A에서 B로 가는 경로가 입력으로 여러개 들어올 수 있다. 따라서 그 중에서 가장 작은 값을 D[A][B] 에 넣어줘야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include using namespace std;const int INF = 20000000;int D[101][101];int main(){ int n, m; scanf("%d %d", &n, &m); for (int i = 0; i 더보기 1753번 1753번 - 최단 경로 이 문제는 가중치가 있고, 방향이 있는 그래프에서 한점에서 나머지 점까지 최단 거리를 구하므로 다익스트라, 벨만코드, 플로이드 워셜 알고리즘이 있다. 일단 노드의 수가 최대 2만개, 간선의 수가 최대 30만개로 많다. 벨만코드의 시간 복잡도는 O(VE) 이므로 2만*30만= 60억으로 , 1억을 1초라 하면 60초나 걸린다. 또한 플로이드 워셜 알고리즘은 O(V^3) 이므로 더 많은 시간이 걸린다. 따라서 가장 빠른 다익스트라 알고리즘을 사용해야 한다. 다익스트라 알고리즘도 2가지 방식이 있다. 하나는 priority queue 를 사용하는 방법과, 그렇지 않은 방법. 일단 priority queue 를 사용하면 O(ElogV) = 30만 * 15 = 450만으로 충분히 사용할 .. 더보기 1504번 1504번 - 특정한 최단 경로 1번 정점에서 N번 정점까지 가는데 A,B를 무조건 거쳐야 한다. 그러기 위해서는 1->A->B->N 이거나 1->B->A->N 이어야 한다.( 문제에서 간선을 여러번 지나쳐도 되기 때문에, 다른 케이스는 고려하지 않아도 된다.) 따라서 첫번째 경우나, 두번째 경우에서 최솟값을 찾으면 된다. 편의상 D[i][j] 를 i 에서 j 가는 최단거리라고 하면 , 첫번째 경우는 D[1][A] + D[A][B] + D[B][N] 이고, 두번째 경우는 D[1][B] + D[B][A} + D[A][N] 이 된다. 여기서 D[A][B]=D[B][A] 이므로 한번의 다익스트라 알고리즘으로 구하고, D[1][A] 와 D[1][B]는 시작점을 1로 하는 다익스트라 알고리즘으로 구하고, D[B].. 더보기 11779번 11779번 - 최소 비용 구하기 2 1916번과 동일한 문제인데, 최단 거리에 이르는 경로와 그 경로에서 정점의 갯수까지 구하는 문제이다. BFS, 다익스트라, 벨만 포드는 모두 parent 배열을 이용해서 경로를 구할 수 있다. distance 값이 바뀔 때, parent[next]=now 로 바꿔주면 되기 때문이다. 이를 이용해서 , 경로 상에서 정점의 갯수와 순서까지 알아낼 수 있다. 이를 order 배열을 이용하거나 stack을 이용해서 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273.. 더보기 1916번 1916번 - 최소 비용 구하기 문제를 그래프 모델로 바꾸고, 주어진 시작점과 끝점에서의 최단 거리를 구하면 된다. 가중치가 있고, 최단거리를 구하기 때문에 bfs 가 아닌 다익스트라 알고리즘을 사용하면 된다. 다익스트라 알고리즘은 두가지 방식으로 풀 수 있는데, 첫번째는 우선 순위 큐를 이용하는 방법으로 O(ElogV) 의 시간복잡도, 두번째는 우선 순위 큐를 이용하지 않는 방법으로 O(VE)의 시간복잡도( 연결리스트로 풀 경우). 나는 우선 순위 큐를 이용해서 문제를 풀었다. 다익스트라로 풀어보는 첫 문제라서, 우선 순위 큐를 쓸때랑, 쓰지 않을 때 방법이 자꾸 섞여서 생각났다. 더 풀어보면서 확실히 다익스트라를 두가지 방식으로 푸는걸 잡아야겠다. 우선 순위 큐로 풀 때는, 방문을 확인하는 배열이 따.. 더보기 1865번 1865번 - 웜홀 11657 타임머신과 같이, 음수 간선이 있는 그래프에서 최단 거리를 구하는 벨만 포드 알고리즘을 쓰면 된다. 근데 웜홀 문제는 음수 싸이클이 존재하는지 여부만 확인하면 된다. 음수 싸이클이 존재하면, 충분히 음수 싸이클을 돈 뒤에 양수 간선을 이동해서 시작점으로 이동하면, 항상 시작점에서 출발할 때보다 더 이른 시간에 도착하기 때문이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include#includeusing namespace std; co.. 더보기 11657번 11657번 - 타임 머신 그래프 상에서 최단 거리를 구하는 알고리즘으로 풀면 된다. 단, 가중치에서 음의 가중치가 존재 하기 때문에, bfs 나 다익스트라를 쓰면 안되고 벨만 포드 알고리즘을 사용하였다. 음의 싸이클이 존재하는 경우는 ( iter == n && update == true) 일 때 이므로 체크해주면 된다. 그리고 도달할 수 없는 경우는 INF 로 남아있기 때문에, 이를 if문으로 걸러서 출력하면 된다. ##SPFA 풀이 추가 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879.. 더보기 1516번 1516번 - 게임 개발 위상 정렬을 이용한 문제. 2056번 (작업) 이랑 완전 똑같은 문제다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#include#include using namespace std; int indegree[501];int dist[501];int t[501];int main(){ int n; vector v[501]; scanf("%d", &n); for (int i = 1; i 더보기 이전 1 ··· 20 21 22 23 24 25 26 ··· 40 다음