C++66 백준 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. 백준 16398번: 행성 연결 (C++) 문제링크 https://www.acmicpc.net/problem/16398 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자. https://www.youtube.com/watch?v=4wA3bncb64E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=28 코드 #include using namespace std; #define X first #define Y second int n; vect.. 2024. 2. 3. 이전 1 ··· 3 4 5 6 7 8 9 ··· 17 다음