전체 글 썸네일형 리스트형 1956번 1956번 - 운동 싸이클을 구하는 문제이다. 나는 우선 플로이드 워셜 알고리즘을 통해 모든 쌍에 대한 최단거리를 구하였다. 그리고 정점 i 에서 다시 i 로 돌아오는 가장 최단거리는 i 에서 한 정점 k 로 가는 최단거리 + k 에서 다시 i 로 가는 최단거리이기 때문에 이 점을 이용해서 최단거리 싸이클을 구할 수 있었다. ##주의할 점 - i 에서 i 로 돌아오는 값을 처음에 D[i][i] = 0 이라고 놓으면 , 싸이클을 구할 수 없기 때문에, D[i][i] 는 INF 로 초기화 한다 ##다시 깨달은 점 - D[i][i] 를 INF 로 초기화 했기 때문에, 그냥 정답을 D[i][i] 값 중 최소값을 구하면 된다. i 로 돌아오는 싸이클까지 다 계산됨! 12345678910111213141516171.. 더보기 1507번 1507번 - 궁금한 민호 일단 처음에 주어진 입력값을 가지고 플로이드 알고리즘을 다시 수행했다. 그렇게 되면 모든 간선이 연결되어 있게 된다. 그 중에서 이제 삭제할 간선을 선택해야 한다. 삭제할 간선은 i - j 가 있고, i 에서 k를 거쳐서 j 로 가는 i - k - j 가 있다고 할 때, 현재 i 와 k 와 j 정점은 세개의 간선으로 삼각형으로 연결되어 있을 것이다. 그리고 우리는 i - j 의 최단 거리를 안다. 이를 통해 세가지 경우의 수를 알 수 있다. 1번째 경우 - D[i][j] > D[i][k] + D[k][j] 는 불가능한 경우이다. 우리는 D[i][j] 값이 최솟값인 걸 문제에서 줬기 때문이다. 그러므로 -1 출력 2번째 경우 - D[i][j]==D[i][k] + D[k][j] 는.. 더보기 1389번 1389번 - 케빈 베이컨의 6단계 법칙 2달전에 처음 풀 때는 DFS를 이용해서 각각의 사람마다 DFS를 전부 돌렸었다. 그런데 이번에 다시 풀 때는 플로이드 워셜 알고리즘을 통해서 풀 수 있었다. DFS로 풀 때보다 시간이 훨씬 줄었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include using namespace std;int D[101][101];int ans[101];const int INF = 987654321;int main(){ for (int i = 0; i n >> m; for (int i = 0; i > a >> b; .. 더보기 11780번 11780번 - 플로이드 2 11404 플로이드 문제에서 경로를 구하는 문제가 추가되었다. 플로이드 워셜에서 경로를 구할 때는, D[i][j] 값이 갱신 될때, 2차원 via 배열에 k값을 넣는 것이다. 그렇게 된다면 i 에서 j 를 갈때 꼭 k를 거쳐가야 한다는 뜻이 되기 때문에, 이는 i 에서 k 까지, k에서 j 까지의 경로를 구해서 합치면 되기 때문이다. 그래서 makePath 함수에서 이를 재귀를 통해서 구하도록 하였다. 주의할 점은 via 함수를 처음에 -1로 초기화를 시켜줘야 한다는 점이다. 그리고 makePath 에서 중복되는 값들을 처리하기 위해 pop을 한번 시킨다는 것도 주의해야 한다. 마지막으로 출력할 때, 만약 path 에 1개의 값만 들어있다면, 이는 다른 곳으로 갈 수 없다는 .. 더보기 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.. 더보기 이전 1 ··· 38 39 40 41 42 43 44 ··· 61 다음