반응형
https://www.acmicpc.net/problem/14588
14588번: Line Friends (Small)
Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다.
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/24
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)
오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk
rudalsd.tistory.com
1. 각각의 선분을 priority_queue에 넣어서 닿아 있다면 arr[ N ][ N ] 배열을 1로 초기화해줍니다.
2. 플로이드 와샬 알고리즘을 이용하여 arr 배열을 갱신해줍니다.
3. arr[ i ][ j ]가 0이라면 -1을출력하고 그렇지 않다면 arr[ i ][ j ]를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | #include<iostream> #include<queue> #include<vector> using namespace std; struct node { int num; int pos; char cur; }; struct cmp { bool operator()(node right, node left) { if (left.pos == right.pos) { if (left.cur == 'L') return true; else false; } return left.pos < right.pos; } }; int N, Q; int arr[301][301]; int main() { scanf("%d", &N); priority_queue<node, vector<node>, cmp> pq; for (int i = 1; i <= N; i++) { int a, b; scanf("%d %d", &a, &b); pq.push({ i,a,'L' }); pq.push({ i,b,'R' }); } vector<int> stat; while (!pq.empty()) { const int num = pq.top().num; const int pos = pq.top().pos; const char cur = pq.top().cur; pq.pop(); if (cur == 'L') { for (int& next : stat) { arr[next][num] = 1; arr[num][next] = 1; } stat.push_back(num); } else { for (auto i = stat.begin(); i != stat.end();i++) { if (*i == num) { stat.erase(i); break; } } } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { for (int k = 1; k <= N; k++) { if (arr[j][i] != 0 && arr[i][k] != 0) { if (arr[j][k] == 0) { arr[j][k] = arr[j][i] + arr[i][k]; } else { arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]); } } } } } scanf("%d", &Q); for (int i = 0; i < Q; i++) { int a, b; scanf("%d %d", &a, &b); if (arr[a][b] != 0) { printf("%d\n", arr[a][b]); } else { printf("-1\n"); } } } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 2517번 - 달리기 (C++) (0) | 2023.05.19 |
---|---|
[ 백준 ] 17612번 - 쇼핑몰 (C++) (0) | 2023.05.18 |
[ 백준 ] 9879번 - Cross Country Skiing (C++) (0) | 2023.05.16 |
[ 백준 ] 2310번 - 어드벤처 게임 (C++) (0) | 2023.05.15 |
[ 백준 ] 1800번 - 인터넷 설치 (C++) (0) | 2023.05.14 |