C++66 백준 11779번: 최소비용 구하기 2 (C++) 문제링크 https://www.acmicpc.net/problem/11779 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 위 설명의 시퀀스를 바탕으로 코드를 구현하여 시작점 st로부터 특정 인덱스를 가진 노드까지 최단거리를 모두 구한다. 추가적으로 위 그림처럼 시작 지점부터 끝 지점 까지 경로를 찾기 위해서 pre 배열을 선언해서 pre배열을 채우고 해당 테이블을 이용해서 경로까지 출력한다. 문제 풀이는 아래 바킹독님 강의 영상을 참고하자. https://www.youtube.com/watch?v=o9BnvwgPT-o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=30 코드 #include using namespace.. 2024. 2. 3. 백준 1753번: 최단경로 (C++) 문제링크 https://www.acmicpc.net/problem/1753 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 위 설명의 시퀀스를 바탕으로 코드를 구현하여 시작점 st로부터 특정 인덱스를 가진 노드까지 최단거리를 모두 구하여 배열에 넣는다 아래 강의를 참고하자. https://www.youtube.com/watch?v=o9BnvwgPT-o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=30 코드 #include using namespace std; #define X first #define Y second int v,e,st; // {비용, 정점 번호} vector adj[20005]; const int IN.. 2024. 2. 3. 백준 21940번: 가운데에서 만나기 (C++) 문제링크 https://www.acmicpc.net/problem/21940 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 쉽게 해결할 수 있다. 풀이 방법은 다음과 같다. 플로이드 알고리즘을 통해서 각 노드 사이의 최단 거리를 계산 해 놓는다. 우선순위 큐를 활용하여 를 넣어서 왕복 시간이 가장 적은 도시를 바로 꺼낼 수 있게 만든다. 왕복 시간이 가장 작은 것이 가장 위쪽에 존재하므로 우선 해당하는 도시의 번호를 출력한다. 왕복 시간이 가장 작은 것이 여러 개라면 해당 도시 번호까지 전부 출력한다. 위 설명의 시퀀스를 이해하고 아래 코드를 참고하자. 코드 #include using namespace std; int n, m, a, b, c, k, num, ans_min; vector friends.. 2024. 2. 3. 백준 1238번: 파티 (C++) 문제링크 https://www.acmicpc.net/problem/1238 풀이방법 해당 문제는 플로이드 알고리즘 및 다익스트라 알고리즘 모두 사용하여 해결 할 수 있다. 플로이드 알고리즘 플로이드 알고리즘을 이용하여 쉽게 해결할 수 있다. 풀이 방법은 다음과 같다. 플로이드 알고리즘을 통해서 각 노드 사이의 최단거리를 계산 해 놓는다. 단 방향이므로 특정 노드에서 특정 노드로 갈 때와 올 때 거리가 다를 수 있으므로 그 두 개를 더한 값을 MAX값과 비교하고, 더 큰 값을 다시 MAX에 저장한다. 위 설명의 시퀀스와 그래프 그림을 통해서 문제를 이해하고 아래 코드를 참고하자. 다익스트라 알고리즘 solve 함수를 만들어서 st,en인자를 받아서 st부터 en까지 최단 경로를 바로 구할 수 있게 만든다... 2024. 2. 3. 이전 1 2 3 4 5 6 7 8 ··· 17 다음
