[C++] 백준 11404번 플로이드 - 다시 풀어야함

플로이드-와샬 알고리즘을 사용해서 푸는 문제인데,

다익스트라를 사용해서 풀었다.

 

나중에 플로이드-와샬을 공부한 후 다시 풀어봐야겠다.

 

다익스트라 풀이

 

사용한 STL과 변수

다익스트라는 BFS와 비슷하다. 따라서 queue를 사용해야 한다. queue STL을 사용했다.

그리고 인접리스트에서 번호와 비용을 저장하기 위해 vector STL을 사용했다.

각 도시의 개수 vertexCnt,

버스 노선의 개수 edgeCnt,

정답배열인 answer배열,

그리고 해당 도시를 방문했는지를 저장하는 visit 배열이 있다.

방문 기록을 초기화함과 동시에 각 방문했을 때 비용을 최대값으로 초기화 해주는 메서드

answer 배열은 정답(한 정점에서 특정 정점까지의 비용을 저장하는 배열)을 저장한다.

미리 1억을 넣어주어서, 만일 특정 정점까지 가는 비용이 발생했을 때 초기에는 갱신이 될 수 있도록 1억을 넣어준다.

 

메인함수

도시의 개수와 버스 노선의 개수를 입력받는다.

방향이 있는 그래프이다.

시작 정점, 도착 정점, 비용을 입력받고 인접리스트[시작 정점]에 정보를 넣어놓는다.

그리고 1번부터 N개까지의 정점들에서 초기화를 시켜준 후 다익스트라 메서드를 진행한다.

 

다익스트라가 종료된 후에, 만일 각 정점마다 정답 배열의 값이 1억이라면 찾지 못했다는 뜻이므로 0으로 초기화 해준다.

그리고 해당 배열의 값을 출력한다.

 

다익스트라 메서드

priority_queue를 사용해서 다익스트라를 진행한다.

BFS와 크게 다르지 않다.

• 방문 기록을 큐에 넣을 때가 아닌, 해당 정점에서 탐색을 시작할 때 기록한다.
• 해당 정점에 도달했을 때는, 이미 해당 정점까지의 비용이 최소인 상태이다.

가 중점적이다.

탐색을 하면서, 현재 저장중인 비용(answer[찾는 정점][특정 정점])보다 작은 비용이 있다면

우선순위 큐에 넣어주면서 탐색한다.

 

만일 방문했던 적이 있다는 것은 해당 정점까지의 최소값이 이미 갱신됐다는 뜻이다.

 

+@ 만일 마지막 조건에서 최소값만 pq에 넣는 가지치기를 하지 않는다면..

정답은 맞지만 시간이 엄청나게 걸린다.

다른 문제에서는 틀릴 수도 있다.

다익스트라에서는 최소값만 우선순위 큐에 넣는 것이 중요하다.

 

다익스트라로 풀었는데,

다익스트라가 풀이법이 아니라고 한다.

나중에 플로이드-와샬을 공부해서 풀어봐야겠다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.