[ 해결 방법 ]제목처럼 플로이드 와셜 알고리즘을 이용해서 풀면된다. 줄여서 플로이드 알고리즘은 다이나믹 프로그래밍을 이용해서 모든 노드간의 최단거리를 구하는 알고리즘이다.다이나믹 프로그래밍을 구현하기 위한 점화식은 dp[i][j] = dp[i][k] + dp[k][j] 이다.여기서 i는 시작 노드, j는 도착 노드, k는 경유할 노드이다.i노드에서 k노드를 경유해서 j노드로 가는 경로가 i노드에서 j로 바로 가는 경로보다 짧으면 위의 점화식을 적용하면 된다. 문제에서 경로정보 중에 불필요한 정보가 들어온다.3 5 1로 들어온 입력 데이터가 나중에 3 5 10으로 들어올 때도 있다. 이 것만 걸러서 플로이드 와셜 알고리즘을 작성해주면 된다.[ 코드 ]#include #define MAX 101#defin..
https://www.acmicpc.net/problem/1389 [ 나의 해결법 ]다익스트라 알고리즘을 이용해서 문제를 풀었다. 사람1을 시작해서 다익스트라 알고리즘을 진행하면, 사람1과 다른 사람들과의 최단거리를 배열 dist에 구할 수 있다. 배열 dist의 모든 원소를 더하면 사람1의 케빈 베이컨의 값이 나온다.이런 식으로 사람1부터 N명까지 진행하면서 케빈 베이컨 값이 최소의 유저를 찾으면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include #include #include #..
https://www.acmicpc.net/problem/1238 [ 나의 해결법 ]이 문제는 다익스트라 알고리즘을 이용해서 풀면 된다. 그런데 그냥 다익스트라 알고리즘으로 풀면 시간초과가 난다. 시간복잡도를 계산하면 10억이 훌쩍 넘는다. 3중 for문을 돌기 때문이다.다른 사람들의 질문들을 보니 플로이드 와샬 알고리즘을 이용한 사람도 있다. 그런데 나는 우선순위 큐를 이용한 알고리즘을 사용할 것이다. 코드는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include #in..
다익스트라 알고리즘에 대해 자세히 설명된 곳을 추천한다.http://www.playsw.or.kr/repo/cast/105 우선 위 주소로 가서 다익스트라 알고리즘이 어떻게 동작하는지 한번 살펴보길 추천한다. 단계별로 설명되어 있기 때문이 차근 차근 읽어보면 쉽게 이해할 수 있다. 내가 이해한 다익스트라 알고리즘은 출발지로부터 갈 수 있는 노드의 최단 거리를 모든 노드를 방문할 때까지 계속 갱하는 방법이다. 1. 먼저, 집에서 갈 수 있는 곳을 그림의 표에서 거리 칸에 써 넣는다. 2. 그리고 집에서 갈 수 있는 곳은 미용실, 슈퍼마켓, 영어학원 중에서 최단거리인 미용실로 간다. 3.다시 미용실에서 갈 수 있는 곳은 슈퍼마켓, 은행이다.(집은 이미 방문했으니 패스~)여기서 슈퍼마켓으로 가는 경로는 집에서..