다익스트라

[C++] 백준 11779번 최소비용 구하기 2

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 문제. BaaaaaaaaaaarkingDog 님의 0x1D강 - 다익스트라 알고리즘 에 수록된 문제이다. 특정 도시에서, 특정 목적지까지 최소 비용을 구할 뿐만 아니라 경로까지 출력해야 하는 문제. 문제 해석 어려운 조건은 없고 특정 도시에서 다른 도시까지 가는 데 최소 비용을 출력하면 된다. 이 때 최소 비용 뿐만 아니라, 해당 목적지까지 가는 경로도 출력해야 한다. 코드 /* * 백준 11779번 최소비용 구하기 2 ..

[C++] 백준 13549번 숨바꼭질3

다익스트라 문제. 이 문제는 처음에 BFS로 접근했는데 자꾸 틀렸습니다. 가 나왔다. 게시판을 참고하고 나서 다익스트라로 풀었다. 그런데 사람들을 보니 우선순위 큐 + BFS이면 풀 수 있다고 했다. 나도 우선순위 큐 + BFS로 시도했었는데 왜 못풀었을까..흠.. 문제풀이 이 문제는 다익스트라로 풀어야 한다. 왜냐하면 이전의 숨바꼭질 문제들은 +1, -1, *2의 시간초과가 모두 같았지만, 이번 문제의 경우 *2가 걸리는 시간이 0초이다. 따라서 *2들 먼저 모두 탐색한 후에 또 거기서 +1, -1 *2들 먼저.. 이런식으로 탐사해야한다. /* * 백준 13549번 숨바꼭질3 * https://www.acmicpc.net/problem/13549 * 그래프 탐색 이론 - 다익스트라 * 다익스트라에서는 ..

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

플로이드-와샬 알고리즘을 사용해서 푸는 문제인데, 다익스트라를 사용해서 풀었다. 나중에 플로이드-와샬을 공부한 후 다시 풀어봐야겠다. 다익스트라 풀이 다익스트라는 BFS와 비슷하다. 따라서 queue를 사용해야 한다. queue STL을 사용했다. 그리고 인접리스트에서 번호와 비용을 저장하기 위해 vector STL을 사용했다. 각 도시의 개수 vertexCnt, 버스 노선의 개수 edgeCnt, 정답배열인 answer배열, 그리고 해당 도시를 방문했는지를 저장하는 visit 배열이 있다. answer 배열은 정답(한 정점에서 특정 정점까지의 비용을 저장하는 배열)을 저장한다. 미리 1억을 넣어주어서, 만일 특정 정점까지 가는 비용이 발생했을 때 초기에는 갱신이 될 수 있도록 1억을 넣어준다. 도시의 개..

[C++] 백준 10282번 해킹

다익스트라의 기초적인 문제. 다익스트라란? 그래프에서 시작점이 있을 때, 시작점에서부터 최단 거리로 한 점씩 이동해보며 해당 점의 최소거리를 확정해 나가는 알고리즘이다. 이 때, 특정 점에서 다른 점들까지의 거리를 구한다는 뜻은 그 특정 점까지의 최단 거리는 확정됐다는 뜻이다. 그래프 이론에서 중요한 알고리즘이다. 이 때 모든 간선치는 양의 정수라고 가정한다. 다익스트라는 머리로는 그리기가 쉬운데, C++에서 구현하려면 복잡한 문법을 많이 알아야 한다. 내 구현 기준으로는 pair : pair 자료형은 특정 자료형 두개를 동시에 저장할 수 있다. make_pair(1, 2) 혹은 {1, 2} 이런 식으로 사용 가능하다. priority_queue : 우선순위 큐는 T 자료형을 container(vecto..