14938 서강그라운드
아 왜~.~.~.~.~!맞왜틀~~.~.~!!!!!!!!!!
그러나 컴퓨터는 틀리지 않는다.
이전에 스터디하면서 봤던 플로이드 워셜 알고리즘을 사용해서 풀었다. 반례를 찾고 싶은데 내 머리로는 벽에 부딪혔다. 찾아본 예시에서는 모두 잘 동작하는데 어디가 문제일까?
이 문제의 풀이를 찾아봤는데 굉장히 다양한 방법으로 풀 수 있는 문제였다. 어떤 사람은 dfs를, 어떤 사람은 다익스트라를, 어떤 사람은 나처럼 플로이드워셜 알고리즘을 사용해서 풀었다.
<실패코드>
#include <iostream>
#include <algorithm>
using namespace std;
int item[101];
int graph[101][101];
int n, m, r, max_ans, temp;
void set_graph()
{
for (int i = 0; i < 101; i++)
{
for (int j = 0; j < 101; j++)
{
if (i == j)
graph[i][j] = 0;
else
graph[i][j] = 1e9;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> r >> m;
for (int i = 1; i <= n; i++)
cin >> item[i];
set_graph();
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
graph[a][b] = c;
graph[b][a] = c;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
max_ans = 0;
for (int i = 1; i <= n; i++)
{
temp = 0;
for (int j = 1; j <= n; j++)
{
if (graph[i][j] <= r)
{
temp += item[j];
}
}
max_ans = max(max_ans, temp);
//cout << "ans" << i << "의 값은" << temp << "이고 max_ans의 값은 " << max_ans << "입니다." << endl;
}
cout << max_ans;
return 0;
}11780 플로이드2
위의 문제와 비슷한 플로이드 워셜 알고리즘 문제였다. 그러나 조금 다른 점은 비용뿐만 아니라 경로까지 출력해야 되는 부분이었다. 경로 출력은 dfs를 사용했는데, 그 부분을 생각해내지 못해서 많은 시간이 걸렸다.
나는 블로그를 참고해서 코드를 짰다. 기본적인 그래프는 배열로 구현하되 경로를 출력하기 위해 벡터를 사용했다.
<최단 경로 출력 로직>
- 플로이드 워셜 알고리즘을 수행하여 최단거리가 갱신될 때, 거치게 되는 노드를 route 배열에 입력받는다.
- route 배열의 값이 0이 아니라면 중간 노드가 존재하는 것이므로 이를 조건으로 이용해 dfs함수를 구현한다
- 시작노드와 끝 노드를 인자로 받은 뒤
route[시작노드][끝노드] == 0이라면 벡터에 시작노드와 끝 노드를 push하고 재귀를 멈춘다.route[출발노드][도착노드] != 0이라면(출발노드, route[출발노드][도착노드])/(route[출발노드][도착노드], 도착노드)를 재귀 인자로 보낸다.- 재귀를 두번 돌면서 중간 노드가 중복으로 push되므로 pop을 수행한다.
dfs는 활용 가능성이 무궁무진한 것 같다. 이제 dfs/bfs에 어느정도 익숙해졌다고 생각했는데 이런 응용은 생각해내지 못했다. 또한 플로이드 워셜 알고리즘을 혼동하며 3중 반복문을 사용할 때 인덱스를 잘못 설정하는 실수를 했다. 이전에 정리한 글을 보며 잘못 이해한 부분을 바로잡았으나 머릿속에 있는 코드라고 자만했던 것이 문제였던 것 같다.
이제 경로를 저장하는 방법도 알았고 플로이드 워셜 알고리즘의 작동 원리도 다시 정리했으니 두번 실수하는 일은 없도록 하자.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> dir;
int graph[101][101];
int route[101][101];
int n, m;
void set_graph()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
graph[i][j] = 1e9;
}
}
}
void new_route(int start, int end)
{
if (route[start][end] == 0)
{
dir.push_back(start);
dir.push_back(end);
return;
}
new_route(start, route[start][end]);
dir.pop_back();
new_route(route[start][end], end);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
set_graph();
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
graph[a][b] = min(graph[a][b], c);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
if (j == k)
continue;
if (graph[j][k] > graph[j][i] + graph[i][k])
{
graph[j][k] = graph[j][i] + graph[i][k];
route[j][k] = i;
}
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (graph[i][j] != 1e9)
cout << graph[i][j] << " ";
else
cout << 0 << " ";
}
cout << "\n";
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (graph[i][j] == 1e9)
cout << 0;
else
{
dir.clear();
new_route(i, j);
cout << dir.size() << " ";
for (int k = 0; k < dir.size(); k++)
cout << dir[k] << " ";
}
cout << "\n";
}
}
}
겉촉속촉