백준 BOJ 6185번 : Clear And Present Danger
문제 난이도 : Gold V
알고리즘 분류 : 플로이드-워셜
노드와 노드 사이의 거리로 구성된 인접 행렬이 주어질 때 1번 노드들을 거쳐 주어지는 M개의 노드들을 순서대로 방문하는 경로의 최단 거리를 구하는 문제이다.
플로이드-워셜 알고리즘을 사용하여 노드 간 최단 경로를 구하고, M개의 이동에 대해 경로의 합을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(M);
for(int i=0; i<M; i++) cin >> v[i];
vector<vector<int>> dis(N+1, vector<int>(N+1));
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) cin >> dis[i][j];
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int ans = 0;
for(int i=1; i<M; i++) ans += dis[v[i-1]][v[i]];
cout << ans << "\n";
}
백준 BOJ 11265번 : 끝나지 않는 파티
문제 난이도 : Gold V
알고리즘 분류 : 플로이드-워셜
N개의 파티가 있고 파티 사이의 거리가 인접 행렬로 주어질 때, 주어진 M개의 커리에 대해 특정 파티장에서 다른 파티장으로 주어진 시간에 이동이 가능한지 여부를 구하는 문제이다.
N이 50 이하이므로 플로이드-워셜 알고리즘을 사용하여 파티 간 최단 거리를 미리 모두 구해놓은 뒤 쿼리가 들어오면 답만 찾아서 출력해주는 방식으로 풀이할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1));
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) cin >> dis[i][j];
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
while(M--) {
int a, b, c; cin >> a >> b >> c;
if(dis[a][b] <= c) cout << "Enjoy other party\n";
else cout << "Stay here\n";
}
}
백준 BOJ 14641번 : Secret Chamber at Mount Rushmore
문제 난이도 : Gold V
알고리즘 분류 : 플로이드-워셜
알파벳 간 변환이 가능한 쌍들이 주어지고, 단어 쌍이 주어질 때 한 단어에서 다른 단어로 변환이 가능한지의 여부를 구하는 문제이다.
각 알파벳을 노드라고 생각하고 변환 가능한 쌍을 간선으로 연결해주면 그래프가 완성된다.
이제 단어의 각 자리에 대해 한 단어의 알파벳에서 다른 단어의 알파벳으로의 경로가 존재하는지의 여부를 구해 하나라도 맞지 않으면 no를 출력해주면 된다.
알파벳의 개수는 26개이므로 플로이드-워셜 알고리즘으로 미리 모든 쌍에 대한 거리를 구해둘 수 있다.
주의해야 할 예외는 같은 알파벳 사이, 즉 변환이 필요 없는 경우하고 두 단어의 길이가 다른 경우이다.
두 단어의 길이가 다른 경우는 모두 no가 되어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(26, vector<int>(26, INT_MAX));
while(N--) {
char a, b; cin >> a >> b;
dis[a - 'a'][b - 'a'] = 1;
}
for(int k=0; k<26; k++)
for(int i=0; i<26; i++)
for(int j=0; j<26; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
while(M--) {
string a, b; cin >> a >> b;
if(a.length() != b.length()) {
cout << "no\n";
continue;
}
bool check = true;
for(int i=0; i<a.length(); i++) {
if(a[i] == b[i]) continue;
if(dis[a[i] - 'a'][b[i] - 'a'] == INT_MAX) check = false;
}
if(check) cout << "yes\n";
else cout << "no\n";
}
}
백준 BOJ 15723번 : n단 논법
문제 난이도 : Gold V
알고리즘 분류 : 플로이드-워셜
N개의 참인 명제가 주어질 때, M개의 명제의 참의 여부를 구하는 문제이다.
명제의 주어와 목적어에 해당하는 알파벳을 노드로 생각하고, 논리 관계를 간선으로 생각하면 그래프를 만들 수 있다.
이 그래프에서 M개의 명제에 대해 주어 노드에서 목적어 노드로 도달이 가능하다면 해당 명제는 참이라고 할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
cin.ignore();
vector<vector<int>> dis(26, vector<int>(26, INT_MAX));
while(N--) {
string str; getline(cin, str);
dis[str[0] - 'a'][str[str.length()-1] - 'a'] = 1;
}
for(int k=0; k<26; k++)
for(int i=0; i<26; i++)
for(int j=0; j<26; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int M; cin >> M;
cin.ignore();
while(M--) {
string str; getline(cin, str);
if(dis[str[0] - 'a'][str[str.length()-1] - 'a'] != INT_MAX) cout << "T\n";
else cout << "F\n";
}
}
백준 BOJ 2224번 : 명제 증명
문제 난이도 : Gold V
알고리즘 분류 : 플로이드-워셜
a => b, b => c와 같은 명제들이 주어질 때, 만족하는 명제의 수와 그 명제들을 모두 구하는 문제이다.
예를 들어 이 예시에서는 a => b, b => c, a => c 3가지를 구할 수 있다.
명제 이름을 노드로, 명제 사이 관계를 간선으로 생각하여 그래프를 만든 뒤 한 정점에서 도달 가능한 다른 모든 정점을 찾아 그 순서쌍을 모두 구해주면 된다.
다만 a => a와 같은 명제는 출력하지 않는다고 하였는데, 입력으로 들어오지 않는다고는 하지 않았으므로 입력으로 들어올 수 있다.
따라서 같은 노드에서 같은 노드를 가리키는 명제에 대한 예외 처리를 해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
cin.ignore();
vector<vector<int>> dis(52, vector<int>(52, INT_MAX));
while(N--) {
string str; getline(cin, str);
int a, b;
if(str[0] >= 'A' && str[0] <= 'Z') a = str[0] - 'A';
else a = str[0] - 'a' + 26;
if(str[str.length()-1] >= 'A' && str[str.length()-1] <= 'Z') b = str[str.length()-1] - 'A';
else b = str[str.length()-1] - 'a' + 26;
dis[a][b] = 1;
}
for(int k=0; k<52; k++)
for(int i=0; i<52; i++)
for(int j=0; j<52; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
vector<pair<int, int>> v;
for(int i=0; i<52; i++)
for(int j=0; j<52; j++) {
if(i == j) continue;
if(dis[i][j] != INT_MAX) v.push_back({i, j});
}
cout << v.size() << "\n";
for(int i=0; i<v.size(); i++) {
if(v[i].first < 26) cout << char(v[i].first + 'A');
else cout << char(v[i].first - 26 + 'a');
cout << " => ";
if(v[i].second < 26) cout << char(v[i].second + 'A');
else cout << char(v[i].second - 26 + 'a');
cout << "\n";
}
}
백준 BOJ 21278번 : 호식이 두 마리 치킨
문제 난이도 : Gold V
알고리즘 분류 : 플로이드-워셜
그래프가 주어질 때 두 지점을 잡아, 두 지점 중 가까운 것에서 모든 노드까지의 왕복 거리의 합이 최소가 되도록 하는 노드 두 개와 그 때의 거리의 합을 구하는 문제이다.
N이 100 이하이므로 플로이드-워셜로 모든 노드 간 거리를 구할 수 있고, 브루트포스로 가능한 모든 두 건물을 잡아 종합 거리를 구해보면 된다.
한 노드에서 자기 자신으로 이동하는 거리를 0으로 설정해주면 편하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b; cin >> a >> b;
dis[a][b] = dis[b][a] = 1;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int a, b, Min = INT_MAX;
for(int i=1; i<=N; i++)
for(int j=i+1; j<=N; j++) {
if(i == j) continue;
int sum = 0;
for(int k=1; k<=N; k++)
sum += min(dis[k][i], dis[k][j]) * 2;
if(sum < Min) {
Min = sum;
a = i, b = j;
}
}
cout << a << " " << b << " " << Min << "\n";
}
백준 BOJ 2219번 : 보안 시스템 설치
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
모든 컴퓨터까지 도달하는 통신 시간의 합이 최소가 되도록 하기 위한 중심 컴퓨터의 번호를 구하는 문제이다.
플로이드-워셜로 모든 컴퓨터 간의 거리를 구하고, 1번부터 N번까지 모두 각 컴퓨터까지 거리의 합을 구해 비교해보면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b, c; cin >> a >> b >> c;
dis[a][b] = dis[b][a] = c;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int ans, Min = INT_MAX;
for(int i=1; i<=N; i++) {
int sum = 0;
for(int j=1; j<=N; j++) sum += dis[i][j];
if(sum < Min) {
Min = sum;
ans = i;
}
}
cout << ans << "\n";
}
백준 BOJ 2458번 : 키 순서
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
N명의 학생 중 M개의 쌍의 키의 비교 관계가 주어질 때, 자신의 키가 몇 번째로 큰 지 알 수 있는 사람의 수를 구하는 문제이다.
키가 몇 번째인지 알려면 모든 사람들에 대해 자신보다 키가 크거나 작은 비교 관계를 알아야 한다.
이것은 모든 노드가 그 노드에서 자신에게 도달할 수 있거나, 자신이 그 노드로 도달할 수 있어야 한다.
왜냐하면 그렇지 않은 노드가 존재할 경우 그 노드와의 비교가 불가능하다는 뜻이기 때문이다.
따라서 플로이드-워셜로 모든 순서쌍에 대한 거리를 구하고 검사해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b; cin >> a >> b;
dis[a][b] = 1;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int ans = 0;
for(int i=1; i<=N; i++) {
bool check = true;
for(int j=1; j<=N; j++)
if(dis[i][j] == INT_MAX && dis[j][i] == INT_MAX) check = false;
if(check) ans++;
}
cout << ans << "\n";
}
참고로 이 문제는 백준 BOJ 6156번 : Cow Contest 문제와 설명만 다를 뿐 풀이가 동일한 문제이다.
백준 BOJ 2617번 : 구슬 찾기
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
N개의 구슬과 M개의 무게 관계가 주어질 때, 무게의 순서가 절대로 (N+1)/2번째가 될 수 없는 구슬의 수를 구하는 문제이다.
일단 다음 둘 중 하나를 만족하면 무게가 (N+1)/2번째가 될 수 없다.
1. 더 무거운 구슬이 (N+1)/2개 이상임
2. 더 가벼운 구슬이 N - (N+1)/2개 초과임
따라서 그래프로 연결 관계를 연결해준 뒤 플로이드-워셜로 모든 노드 쌍에 대한 거리를 구하고, 자신에게 도달할 수 있는 노드의 수가 (N+1)/2개 이상인지와 자신으로부터 도달할 수 있는 노드의 수가 N - (N+1)/2개인지를 검사하여 하나라도 해당될 경우 count 해주면 된다.
이 때 주의해야 할 점은 노드 자기 자신에 대한 거리는 제외하고 count 해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b; cin >> a >> b;
dis[a][b] = 1;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int ans = 0;
for(int i=1; i<=N; i++) {
bool check = false;
int cnt = 0;
for(int j=1; j<=N; j++)
if(i != j && dis[j][i] != INT_MAX) cnt++;
if(cnt >= (N+1)/2) check = true;
cnt = 0;
for(int j=1; j<=N; j++)
if(i != j && dis[i][j] != INT_MAX) cnt++;
if(cnt > N - (N+1)/2) check = true;
if(check) ans++;
}
cout << ans << "\n";
}
백준 BOJ 6135번 : Cow Hurdles
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
그래프가 주어질 때, 주어진 두 점 사이를 이동할 때 이용하는 간선들 중 비용이 가장 큰 간선의 값이 최소가 되도록 하는 경로의 비용이 가장 큰 간선의 비용을 구하는 문제이다.
N이 300 이하이고 쿼리가 엄청 많으므로 결국 모든 노드 쌍 사이의 경로에 대해 최대 비용 간선을 찾아놔야 한다.
따라서 플로이드-워셜 알고리즘을 응용해서 푸는 방법을 생각해볼 수 있다.
만약 경로 갱신이 되는 상태이고 최대 비용 간선을 갱신하려면 dis[i][j]와 max(dis[i][k], dis[k][j]) 중 더 작은 것을 선택하면 된다. (물론 여기서는 distance의 개념이 아니긴 한데 다른 문제 풀다가 일단 그대로 썼다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b, c; cin >> a >> b >> c;
dis[a][b] = c;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX) {
if(i == j || i == k || k == j) continue;
dis[i][j] = min(dis[i][j], max(dis[i][k], dis[k][j]));
}
while(K--) {
int a, b; cin >> a >> b;
if(dis[a][b] != INT_MAX) cout << dis[a][b] << "\n";
else cout << -1 << "\n";
}
}
백준 BOJ 14675번 : 단절점과 단절선
문제 난이도 : Gold V
알고리즘 분류 : 그래프 이론
트리가 주어지고 쿼리들이 어떤 노드나 간선이 단절점 또는 단절선인지를 구하는 문제이다.
주어지는 그래프가 트리임에 주목하자.
트리는 사이클을 가지고 있지 않으므로 말단 노드가 아닌 경우 그 노드는 무조건 단절점이 된다.
따라서 adj size가 2 이상이라면 그 노드는 단절점임을 알 수 있다.
그 다음 간선의 경우 반드시 두 그래프로 분리가 발생하므로 트리의 모든 간선은 단절선에 해당한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<vector<int>> adj(N+1);
for(int i=0; i<N-1; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int M; cin >> M;
while(M--) {
int Q, x; cin >> Q >> x;
if(Q == 1) {
if(adj[x].size() >= 2) cout << "yes\n";
else cout << "no\n";
}
else if(Q == 2) cout << "yes\n";
}
}
백준 BOJ 6191번 : Cow on Skates
문제 난이도 : Gold V
알고리즘 분류 : BFS
2차원 배열이 주어질 때 (1, 1)에서 (N, M)으로 장애물을 피하여 이동하는 최단 경로를 찾아 그 경로에서 지나가는 모든 좌표를 출력하는 문제이다.
먼저 출발점에서 시작하여 벡터에 좌표들을 저장하는 방식은 고려해야 할 점이 너무 많다.
따라서 경로를 먼저 찾고, 역순으로 벡터에 좌표들을 저장하는 방식을 사용하자.
현재 좌표까지의 거리가 x일 때, 인접한 좌표 중 해당 좌표까지의 거리가 x-1인 좌표는 유일하다.
그러므로 이 방식을 사용하여 문제를 풀이할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<char>> v(N+1, vector<char>(M+1));
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++) cin >> v[i][j];
vector<vector<int>> dis(N+1, vector<int>(M+1, -1));
dis[1][1] = 0;
queue<pair<int, int>> q;
q.push({1, 1});
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || ny < 1 || nx > N || ny > M) continue;
if(v[nx][ny] != '.' || dis[nx][ny] != -1) continue;
dis[nx][ny] = dis[x][y] + 1;
q.push({nx, ny});
}
}
int x = N, y = M;
vector<pair<int, int>> u;
u.push_back({N, M});
while(x != 1 || y != 1) {
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || ny < 1 || nx > N || ny > M) continue;
if(dis[nx][ny] == dis[x][y] - 1) {
u.push_back({nx, ny});
x = nx, y = ny;
break;
}
}
}
for(int i=u.size()-1; i>=0; i--)
cout << u[i].first << " " << u[i].second << "\n";
}
백준 BOJ 6462번 : Risk
문제 난이도 : Silver I
알고리즘 분류 : 그래프 탐색
20개의 노드에 대한 그래프가 주어지고, 각 노드 사이의 거리를 구하는 문제이다.
노드 수가 적으므로 플로이드-워셜로 풀어도 되지만 그냥 BFS로 구했다.
그러나 이 문제의 핵심은 그래프 탐색 구현보다도 입출력이 까다롭다는 데 있다.
나의 경우에는 N이 더 이상 들어오지 않을 경우 즉시 종료하는 방식으로 구현했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
for(int t=1; ; t++) {
vector<vector<int>> adj(21);
for(int i=1; i<=19; i++) {
int N;
if(!(cin >> N)) return 0;
while(N--) {
int x; cin >> x;
adj[i].push_back(x);
adj[x].push_back(i);
}
}
cout << "Test Set #" << t << "\n";
int M; cin >> M;
while(M--) {
int a, b; cin >> a >> b;
vector<int> dis(21, -1);
dis[a] = 0;
queue<int> q;
q.push(a);
while(!q.empty()) {
int x = q.front();
q.pop();
if(x == b) {
printf("%2d to %2d: %d\n", a, b, dis[b]);
break;
}
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(dis[y] != -1) continue;
dis[y] = dis[x] + 1;
q.push(y);
}
}
}
cout << "\n";
}
}
백준 BOJ 14588번 : Line Friends (Small)
문제 난이도 : Gold V
알고리즘 분류 : 그래프 탐색
N개의 선분이 주어지고 서로 겹치는 선분끼리는 연결된다고 할 때 두 선분 사이를 이동하려면 몇 개의 연결된 선분을 거쳐야 하는지 구하는 문제이다.
N개의 선분에 대해 모든 가능한 쌍을 비교해보면서 연결 여부를 확인하고, 연결 상태일 경우 그래프의 두 노드를 간선으로 연결해준다.
그런 다음 탐색을 돌려서 거리를 구해주면 된다.
참고로 이 문제에서는 점만 겹쳐도 선분이 겹친 것으로 판단해야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> v(N+1);
for(int i=1; i<=N; i++) cin >> v[i].first >> v[i].second;
vector<vector<int>> adj(N+1);
for(int i=1; i<=N; i++)
for(int j=i+1; j<=N; j++) {
bool check = false;
if(v[i].first <= v[j].first && v[j].first <= v[i].second && v[i].second <= v[j].second) check = true;
if(v[j].first <= v[i].first && v[i].first <= v[j].second && v[j].second <= v[i].second) check = true;
if(v[i].first <= v[j].first && v[j].second <= v[i].second) check = true;
if(v[j].first <= v[i].first && v[i].second <= v[j].second) check = true;
if(check) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
int M; cin >> M;
while(M--) {
int a, b; cin >> a >> b;
vector<int> dis(N+1, -1);
dis[a] = 0;
queue<int> q;
q.push(a);
bool check = false;
while(!q.empty()) {
int x = q.front();
q.pop();
if(x == b) {
cout << dis[b] << "\n";
check = true;
break;
}
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(dis[y] != -1) continue;
dis[y] = dis[x] + 1;
q.push(y);
}
}
if(!check) cout << -1 << "\n";
}
}
백준 BOJ 6448번 : Stockbrocker Grapevine
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
N명의 사람 사이에서 두 명 사이에 소문이 퍼지는 시간들이 주어질 때, 몇 번 사람으로부터 시작했을 때 소문이 퍼지는 시간이 가장 빠른지와 그 때의 시간을 구하는 문제이다.
문제를 풀기 위해서는 결국 모든 사람 사이의 소문이 도달하는 시간을 다 알고 있어야 하므로 플로이드-워셜로 풀이하는 것이 바람직하다.
따라서 모든 거리를 구해놓고 최대 도달 시간이 최소인 번호와 그 때의 최대 도달 시간을 구하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N; cin >> N;
if(N == 0) break;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
for(int i=1; i<=N; i++) {
int M; cin >> M;
while(M--) {
int a, b; cin >> a >> b;
dis[i][a] = b;
}
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int ans, Min = INT_MAX;
for(int i=1; i<=N; i++) {
int Max = 0;
bool check = true;
for(int j=1; j<=N; j++) {
if(dis[i][j] == INT_MAX) check = false;
else Max = max(Max, dis[i][j]);
}
if(check && Max < Min) {
Min = Max;
ans = i;
}
}
cout << ans << " " << Min << "\n";
}
}
백준 BOJ 9870번 : Vacation Planning
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
그래프가 주어지고 1~K번 노드는 hub라고 할 때, 주어진 쿼리 a, b에 대해 a에서 최소 하나 이상의 hub를 들렀다가 b로 가는 최단 경로를 구하는 문제이다. (이 때 a 또는 b가 hub여도 된다.)
플로이드-워셜로 모든 경로를 구한 뒤, 1~K에 대해 dis[a][i] + dis[i][b]의 값들을 구해보면서 그 최솟값을 구하면 된다.
만약 1~K인 모든 i에 대해 둘 중 하나 이상이 dis = INF인 경우 cnt가 되지 않는다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K, Q; cin >> N >> M >> K >> Q;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b, c; cin >> a >> b >> c;
dis[a][b] = c;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int cnt = 0, sum = 0;
while(Q--) {
int a, b; cin >> a >> b;
bool check = false;
int Min = INT_MAX;
for(int i=1; i<=K; i++) {
if(dis[a][i] != INT_MAX && dis[i][b] != INT_MAX) {
check = true;
Min = min(Min, dis[a][i] + dis[i][b]);
}
}
if(check) {
cnt++;
sum += Min;
}
}
cout << cnt << "\n" << sum << "\n";
}
백준 BOJ 11147번 : Travelling Tom
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
순서대로 여행할 N개 도시 번호와 도시 사이의 거리가 적힌 인접 행렬이 주어질 때 첫 번째 도시에서 순서대로 N개 도시를 방문하고 다시 돌아오는 최단 경로를 구하는 문제이다.
플로이드-워셜로 모든 도시 간의 최소 거리를 구하고, N개 경로의 합을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
vector<vector<int>> dis(N, vector<int>(N, INT_MAX));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) {
int x; cin >> x;
if(x != -1) dis[i][j] = x;
}
for(int k=0; k<N; k++)
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
bool check = true;
int ans = 0;
for(int i=1; i<=N; i++) {
if(dis[v[i-1]][v[i%N]] == INT_MAX) {
check = false;
break;
}
ans += dis[v[i-1]][v[i%N]];
}
if(check) cout << ans << "\n";
else cout << "impossible\n";
}
}
백준 BOJ 12875번 : 칙령
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
N명의 사람들의 친구 관계가 주어지고, 직접 연결된 친구 사이의 돈의 차이의 최댓값이 주어질 때, N명 중 돈이 가장 많은 사람과 적은 사람의 돈의 차이를 구하는 문제이다.
일단 어떤 두 사람이라도 친구가 아닌 경우 돈의 차이가 무한대가 될 수 있다.
따라서 사람을 노드로, 친구 관계를 간선으로 연결한 그래프에 대해 단절된 두 노드가 존재할 경우 -1을 출력해주면 된다.
그 외에는 (거리가 최대인 두 사람 사이의 거리) x (두 사람 사이의 돈의 차이의 최댓값)이 답이 되므로, 최대 거리를 플로이드-워셜로 구해서 찾아주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N, vector<int>(N, INT_MAX));
for(int i=0; i<N; i++) dis[i][i] = 0;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) {
char c; cin >> c;
if(c == 'Y') dis[i][j] = 1;
}
for(int k=0; k<N; k++)
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int Max = 0;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) {
if(dis[i][j] == INT_MAX) {
cout << -1 << "\n";
return 0;
}
Max = max(Max, dis[i][j]);
}
int ans = Max * M;
cout << ans << "\n";
}
백준 BOJ 13424번 : 비밀 모임
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
방 사이의 연결 관계에 해당하는 그래프가 주어지고, K명의 학생이 한 방으로 모일 때 그 거리의 합이 최소가 되도록 하는 방의 번호를 구하는 문제이다.
플로이드-워셜로 모든 방 사이의 최단 거리를 구한 뒤, N개 방 모두에 대해 K명의 학생이 모이는 경로의 합을 구해서 그 최솟값을 만드는 방 번호를 구하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b, c; cin >> a >> b >> c;
dis[a][b] = dis[b][a] = c;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int K; cin >> K;
vector<int> v(K);
for(int i=0; i<K; i++) cin >> v[i];
int ans, Min = INT_MAX;
for(int i=1; i<=N; i++) {
int sum = 0;
for(int j=0; j<K; j++) sum += dis[v[j]][i];
if(sum < Min) {
Min = sum;
ans = i;
}
}
cout << ans << "\n";
}
}
백준 BOJ 14938번 : 서강그라운드
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
N개의 정점으로 이루어진 그래프가 주어지고, 각 노드 위치에 있는 아이템의 수가 주어질 때, 주어진 거리 내에 있는 노드의 아이템들만 얻을 수 있다면 어떤 노드에 내려야 최대 아이템을 얻을 수 있는지를 찾아 그 최대 아이템 수를 구하는 문제이다.
먼저 N개 노드 각각에 대해 나머지 노드에 도달하는 경로를 모두 파악해야 하므로 플로이드-워셜을 이용하여 거리를 구해준다.
그 다음 N개 노드에 대해 반경 M 이하의 거리로 도달할 수 있는 경로들에 한하여 아이템의 수를 더해주고, 그 값들 중 최댓값을 답으로 구하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
vector<int> v(N+1);
for(int i=1; i<=N; i++) cin >> v[i];
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(K--) {
int a, b, c; cin >> a >> b >> c;
dis[a][b] = dis[b][a] = c;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int ans = 0;
for(int i=1; i<=N; i++) {
int sum = 0;
for(int j=1; j<=N; j++)
if(dis[i][j] <= M) sum += v[j];
ans = max(ans, sum);
}
cout << ans << "\n";
}
백준 BOJ 16958번 : 텔레포트
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
N개 도시의 2차원 좌표가 주어지고, 두 도시 간 이동하는데 걸리는 시간은 맨해튼 거리이며, 텔레포트가 가능한 두 도시 사이에는 M 시간에 이동이 가능하다고 할 때 K개 쿼리로 주어지는 두 도시 사이 최소 이동 시간들을 구하는 문제이다.
쿼리로 모든 쌍이 들어올 수 있으므로 결국 모든 도시 사이의 최소 이동 시간을 구해야 한다.
따라서 플로이드-워셜로 풀어주기 위해 먼저 O(N^2) 시간에 모든 도시 사이의 거리를 구해준다.
그 다음 두 도시 모두 텔레포트가 가능한 경우 M과 기존에 기록되어 있는 시간을 비교하여 최솟값을 설정해준다.
이제 쿼리들에 대해 거리 값만 가져와서 출력해주면 된다.
여담으로 데이터가 조금 무거운 편이라 2초의 제한 시간이 있는 문제에 아래의 C++ 풀이가 1400ms 정도에 돌아간다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int s, x, y; };
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
vector<s> v(N+1);
for(int i=1; i<=N; i++)
cin >> v[i].s >> v[i].x >> v[i].y;
for(int i=1; i<=N; i++)
for(int j=i+1; j<=N; j++) {
dis[i][j] = dis[j][i] = abs(v[i].x - v[j].x) + abs(v[i].y - v[j].y);
if(v[i].s == 1 && v[j].s == 1) dis[i][j] = dis[j][i] = min(dis[i][j], M);
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int K; cin >> K;
while(K--) {
int a, b; cin >> a >> b;
cout << dis[a][b] << "\n";
}
}
백준 BOJ 21940번 : 가운데에서 만나기
문제 난이도 : Gold IV
알고리즘 분류 : 플로이드-워셜
N개의 도시에 대해 M개의 간선이 주어지고, K명의 친구들이 살고 있는 도시에서부터 어떤 도시로 모였다가 돌아가는 왕복 이동을 했을 때 그 왕복 이동 거리가 최대인 사람의 거리가 최소가 되도록 하는 모일 도시를 구하는 문제이다.
플로이드-워셜로 모든 도시 쌍에 대한 최단 거리를 구하고, K명의 사람들이 어떤 도시로 모였을 때 최대 이동 거리가 최소가 되는지를 일일이 다 거리 합을 구해서 비교해보면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b, c; cin >> a >> b >> c;
dis[a][b] = c;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int K; cin >> K;
vector<int> v(K);
for(int i=0; i<K; i++) cin >> v[i];
int Min = INT_MAX;
for(int i=1; i<=N; i++) {
int Max = 0;
for(int j=0; j<K; j++)
Max = max(Max, dis[v[j]][i] + dis[i][v[j]]);
Min = min(Min, Max);
}
for(int i=1; i<=N; i++) {
int Max = 0;
for(int j=0; j<K; j++)
Max = max(Max, dis[v[j]][i] + dis[i][v[j]]);
if(Max == Min) cout << i << " ";
}
cout << "\n";
}
백준 BOJ 1613번 : 역사
문제 난이도 : Gold III
알고리즘 분류 : 플로이드-워셜
N개의 사건에 대해 M개의 두 사건의 앞뒤 순서가 주어질 때, K개의 쿼리에 대해 두 사건 중 어떤 것이 먼저 일어났는지를 구하는 문제이다.
M개의 단방향 간선을 가진 그래프를 만들어서, (a, b) 쿼리에 대해 a → b로 연결이 가능하면 a가 먼저 일어난 것이고 b → a로 연결이 가능하면 b가 먼저 일어난 것이며 두 노드 사이가 단절되었다면 어떤 것이 먼저 일어난 것인지 모르는 것이다.
따라서 그래프를 구현해준 뒤 플로이드-워셜로 일단 모든 두 노드 사이의 거리를 구하고, 쿼리에 대해 두 노드 사이의 거리가 INF인지 아닌지를 파악하여 답을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b; cin >> a >> b;
dis[a][b] = 1;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int K; cin >> K;
while(K--) {
int a, b; cin >> a >> b;
if(dis[a][b] != INT_MAX) cout << -1 << "\n";
else if(dis[b][a] != INT_MAX) cout << 1 << "\n";
else cout << 0 << "\n";
}
}
백준 BOJ 10159번 : 저울
문제 난이도 : Gold III
알고리즘 분류 : 플로이드-워셜
N개 물건들이 있고 두 물건의 무게 관계 M개가 주어질 때, N개 물건 각각에 대해 무게 비교를 알 수 없는 물건들의 개수를 구하는 문제이다.
각 물건을 하나의 노드로 보고, 물건 무게 관계에 따라 단방향 간선으로 연결해준다.
그런 후 두 물건 사이의 연결성을 검사하면 된다.
만약 두 물건에 해당하는 노드 사이가 간선으로 연결되어있지 않다면 그 두 물건은 무게 관계를 알 수 없는 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> dis(N+1, vector<int>(N+1, INT_MAX));
for(int i=1; i<=N; i++) dis[i][i] = 0;
while(M--) {
int a, b; cin >> a >> b;
dis[a][b] = 1;
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
for(int i=1; i<=N; i++) {
int ans = 0;
for(int j=1; j<=N; j++)
if(dis[i][j] == INT_MAX && dis[j][i] == INT_MAX) ans++;
cout << ans << "\n";
}
}
백준 BOJ 5873번 : Distant Pastures
문제 난이도 : Gold III
알고리즘 분류 : 플로이드-워셜
N x N 크기의 목초지가 주어지고, 소는 상하좌우로 인접한 방향으로만 이동하며 같은 종류의 풀 사이는 a의 시간동안, 다른 종류의 풀 사이는 b 시간동안 이동한다고 할 때 이동 시간이 가장 먼 두 위치 사이의 이동 시간을 구하는 문제이다.
결국 모든 쌍에 대해 이동 시간을 확인해보아야 하므로, N x N 모든 칸을 하나의 노드로 보아 N x N개의 노드를 가지는 그래프를 만들어 인접한 위치끼리 a 또는 b의 비용을 가지는 간선으로 연결하여 탐색하면 된다.
N의 크기가 30 이하이므로 노드의 개수는 최대 900개이다.
O(900^3)이면 충분히 돌아갈 수 있으므로 플로이드-워셜로 모든 위치 쌍 사이의 최소 이동 시간을 구해줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
vector<vector<char>> v(N, vector<char>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> v[i][j];
vector<vector<int>> dis(N*N, vector<int>(N*N, INT_MAX));
for(int i=0; i<N*N; i++) dis[i][i] = 0;
for(int i=0; i<N; i++)
for(int j=0; j<N-1; j++) {
if(v[i][j] == v[i][j+1]) dis[i*N+j][i*N+j+1] = dis[i*N+j+1][i*N+j] = M;
else dis[i*N+j][i*N+j+1] = dis[i*N+j+1][i*N+j] = K;
}
for(int i=0; i<N-1; i++)
for(int j=0; j<N; j++) {
if(v[i][j] == v[i+1][j]) dis[i*N+j][(i+1)*N+j] = dis[(i+1)*N+j][i*N+j] = M;
else dis[i*N+j][(i+1)*N+j] = dis[(i+1)*N+j][i*N+j] = K;
}
for(int k=0; k<N*N; k++)
for(int i=0; i<N*N; i++)
for(int j=0; j<N*N; j++)
if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int ans = 0;
for(int i=0; i<N*N; i++)
for(int j=i+1; j<N*N; j++)
if(dis[i][j] != INT_MAX) ans = max(ans, dis[i][j]);
cout << ans << "\n";
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 에라토스테네스의 체, 소수 판별 문제들 풀이 220801 (0) | 2022.08.01 |
|---|---|
| 백준 BOJ 풀이 : 다양한 유형 및 백트래킹 문제들 220731 (0) | 2022.07.31 |
| 백준 BOJ 풀이 : 그래프 이론 문제들 (Silver I ~ Gold) 220729 (0) | 2022.07.29 |
| 백준 BOJ 풀이 220728 (0) | 2022.07.28 |
| 백준 BOJ 풀이 : 각종 Silver 난이도 그래프 문제들 220727 (0) | 2022.07.27 |