자료구조 알고리즘(C++)/플로이드-와샬4 [C++]백준(BOJ) - 17182 우주 탐사선(플로이드-와샬) 난이도 : 골III풀이 시간 : 20분알고리즘 유형 : 플로이드, 백트래킹 풀이 방법 : 플로이드 최단경로, DFS 탐색 문제 링크https://www.acmicpc.net/problem/17182 문제 예시우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. -> 모든 탐색, 최단 거리 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. -> 2차원 행렬로 거리를 표시(인접 행렬)행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에.. 2024. 11. 17. [C++]백준(BOJ) - 2548 키 순서(플로이드-와샬) 난이도 : 골IV알고리즘 유형 : 플로이드-와샬, dfs풀이 방법 : 3중 for문(플로이드-와샬) 문제 링크https://www.acmicpc.net/problem/2458 문제의 예시자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산-> 모든 방법을 탐색한다. a에서 b로 화살표를 그려서 표현하였다.-> 방향 그래프이다. N (2 ≤ N ≤ 500) 인것을 보아 단순 계산을 한다면 O(N^3)으로 풀 수 있습니다.또한, 이 문제는 모든 방법을 탐색해야 하므로 플로이드-와샬을 이용하면 됩니다. 기본적인 min 연산을 하는 플로이드-와샬과 달리 이 문제는 비교를 하는 문제입니다.그렇기 때문에 방향 그래프로 경로가 있을때만 플로이드로 체크만 해주면 됩니다. 플로이드 연산이 완료되면 방향 그.. 2024. 11. 2. [C++]백준(BOJ) - 2660 회장뽑기(플로이드-와샬) 난이도 : 골V알고리즘 유형 : 플로이드-와샬, bfs풀이 방법 : 3중 for문(플로이드-와샬) 문제 링크https://www.acmicpc.net/problem/2660 문제의 예시월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 몇 사람을 통하면 모두가 서로 알 수 있다. -> 모두 연결되어있음 가까운 정도에 따라 점수를 받게 된다.회장은 회원들 중에서 점수가 가장 작은 사람이 된다. -> 거리에 따른 정답 A와 B가 친구면, 1점A와 B가 친구고 B와 C가 친구면 A는 2점이렇게 점수를 계산해 두루두루 친한 사람들 회장으로 뽑는 문제입니다. -> 최단 거리라는 것을 알 수 있고, 모두 계산하기 때문에 플로이드로 풀 수 있다. -> 여기서 양방향 그래프라는 것도 알 수 있다. (B, .. 2024. 10. 30. [C++]백준(BOJ) - 11403 경로 찾기(플로이드-와샬) 난이도 : 실I알고리즘 유형 : 플로이드-와샬풀이 방법 : 3중 for문 문제 링크https://www.acmicpc.net/problem/11403 이 문제는 플로이드-와샬의 기본 문제이며, 입력에 인접 행렬이 주어지고 최단경로는 구하는 문제입니다.그리고 N이 100이 최대라는 점에서 인접 행렬 + 최단경로 = 플로이드 라는 것을 알 수 있습니다. 플로이드는 3중 for문으로 만들었으며 주의 사항은 최단경로이기 때문에 경로가 없는 지점은 0이 아닌 최대값을 넣어야합니다. 저같은 경우는 0x3f3f3f3f + 0x3f3f3f3f 가 overflow가 발생하지 않도록 최대값을 넣어주었습니다. #include using namespace std;int n;const int inf = 0x3f3f3f3f;.. 2024. 10. 28. 이전 1 다음