분류 전체보기79 백준 1238번: 파티 (C++) 문제링크 https://www.acmicpc.net/problem/1238 풀이방법 해당 문제는 플로이드 알고리즘 및 다익스트라 알고리즘 모두 사용하여 해결 할 수 있다. 플로이드 알고리즘 플로이드 알고리즘을 이용하여 쉽게 해결할 수 있다. 풀이 방법은 다음과 같다. 플로이드 알고리즘을 통해서 각 노드 사이의 최단거리를 계산 해 놓는다. 단 방향이므로 특정 노드에서 특정 노드로 갈 때와 올 때 거리가 다를 수 있으므로 그 두 개를 더한 값을 MAX값과 비교하고, 더 큰 값을 다시 MAX에 저장한다. 위 설명의 시퀀스와 그래프 그림을 통해서 문제를 이해하고 아래 코드를 참고하자. 다익스트라 알고리즘 solve 함수를 만들어서 st,en인자를 받아서 st부터 en까지 최단 경로를 바로 구할 수 있게 만든다... 2024. 2. 3. 백준 11780번: 플로이드2 (C++) 문제링크 https://www.acmicpc.net/problem/11404 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 각 노드에 대한 최단 경로를 모두 구하여 한번에 출력하고 단순히 최단 거리 뿐만 아니라 특정 노드에서 노드로 이동하는 최단 경로가 어떻게 진행되는지도 출력해야 하는 문제다. 따라서 경로 복원에 필요한 nxt배열을 추가로 삽입하여 문제를 해결할 수 있다. 해당 문제에 대한 상세 풀이는 아래 바킹독님 영상을 참고하자. 또한 플로이드 알고리즘이나 경로 복원에 대한 개념이 부족하면 아래 영상을 통해 알고리즘에 대한 개념을 익히자. https://www.youtube.com/watch?v=dDDy2bEZRA8 코드 #include using namespace std; const int I.. 2024. 2. 3. 백준 11404번: 플로이드 (C++) 문제링크 https://www.acmicpc.net/problem/11404 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 각 노드에 대한 최단 경로를 모두 구하여 한번에 출력하는 문제이다. 해당 문제에 대한 상세 풀이나 플로이드 알고리즘에 대한 이해가 필요하면 아래 영상을 참고하자. https://www.youtube.com/watch?v=dDDy2bEZRA8 코드 #include using namespace std; const int INF = 0x3f3f3f3f; int d[105][105]; int n, m; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i > a >> b >> c; d[a].. 2024. 2. 3. 백준 1647번: 도시 분할 계획 (C++) 문제링크 https://www.acmicpc.net/problem/16398 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자. https://www.youtube.com/watch?v=4wA3bncb64E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=28 우선 마을 하나하나를 그래프의 노드라고 생각한다. 그 상태로 최소 신장 트리를 만든다. 그럼 모든 마을이 연결되어있고 가중치의 합이 최소인.. 2024. 2. 3. 이전 1 ··· 3 4 5 6 7 8 9 ··· 20 다음
