BOJ_1719
😄 다익스트라로 풀어냈는데, 경로를 저장해야하는 점에서 기존의 문제와 다른 것 같다.
1719번: 택배
다익스트라 알고리즘
으로 각 노드사이의 최소 거리를 찾음과 동시에 거쳐간 노드를 저장해줘야 최단거리 중 가장 처음에 갔던 노드를 뽑아낼 수 있다.- 일단 일반
다익스트라 알고리즘
에서 path에 전에 거쳐간 노드를 저장해준다.
💻 다익스트라 알고리즘
void bfs(int node)
{
vector<int> dist(n + 1, 987654321);
priority_queue<pair<int, int> > q;
q.push(make_pair(node, 0));
dist[node] = 0;
while(!q.empty())
{
int cur = q.top().first;
int cost = -q.top().second;
q.pop();
if(cost > dist[cur])
continue;
for (int i = 0; i < v[cur].size(); i++)
{
int next = v[cur][i].first;
int ncost = v[cur][i].second;
if(dist[next] > cost + ncost)
{
dist[next] = cost + ncost;
q.push(make_pair(next, -dist[next]));
path[next] = cur;
}
}
}
for (int i = 1; i <= n;i++)
{
if(node == i)
ans[node][i] = "-";
else{
int t = i;
while (path[t] != node)
{
t = path[t];
}
ans[node][i] = to_string(t);
}
}
}
- 위의 코드는 일반적인
다익스트라 알고리즘
이다. 여기서 path 배열을 추가해 최소거리로 갱신될 때마다, 그 전에 거쳐갔던 노드를 저장해준다. - 후에
for문
을 통해 자신이 거쳐간 path를 시작 노드가 나올때까지while
을 돌려주고 답이 나오면 이를 ans값에 저장해준다.
💻전체코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
using namespace std;
#define endl "\n"
vector<pair<int,int> > v[201];
int path[201];
string ans[201][201];
int n, m;
void bfs(int node)
{
vector<int> dist(n + 1, 987654321);
priority_queue<pair<int, int> > q;
q.push(make_pair(node, 0));
dist[node] = 0;
while(!q.empty())
{
int cur = q.top().first;
int cost = -q.top().second;
q.pop();
if(cost > dist[cur])
continue;
for (int i = 0; i < v[cur].size(); i++)
{
int next = v[cur][i].first;
int ncost = v[cur][i].second;
if(dist[next] > cost + ncost)
{
dist[next] = cost + ncost;
q.push(make_pair(next, -dist[next]));
path[next] = cur;
}
}
}
for (int i = 1; i <= n;i++)
{
if(node == i)
ans[node][i] = "-";
else{
int t = i;
while (path[t] != node)
{
t = path[t];
}
ans[node][i] = to_string(t);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m;i++)
{
int a, b, dis;
cin >> a >> b >> dis;
v[a].push_back(make_pair(b,dis));
v[b].push_back(make_pair(a, dis));
}
for (int i = 1; i <= n;i++)
{
bfs(i);
}
for (int i = 1; i <= n;i++)
{
for (int j = 1; j <= n;j++)
cout << ans[i][j] << " ";
cout << endl;
}
}
경로를 저장하는 부분에서 조금 막혀서 검색을 통해 풀어냈다..😭 경로 저장도 대충 연쇄적으로 이루어진다는 점을 알았다.
Author And Source
이 문제에 관하여(BOJ_1719), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@luck2901/BOJ1719저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)