[Algorithm]Baekjoon 1719번 : 택배

https://www.acmicpc.net/problem/1719

1719번: 택배

struct Node
{
    int node;
    int weight;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.weight < b.weight;
    }
};
 
int n, m, a, b, c;
vector<vector<Node>> graph(201);
int answer[201][201];
int dist[201] = { 0 };
 
void dij(int start)
{
    memset(dist, 0x3f, sizeof(dist));
 
    dist[start] = 0;
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ start,0 });
 
    int parents[201] = { 0 };
 
    while (!pq.empty())
    {
        int curNode = pq.top().node;
        int curWeight = pq.top().weight;
        pq.pop();
 
        if (dist[curNode] < curWeight) continue;
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            int nextWeight = graph[curNode][i].weight;
 
            if (curWeight + nextWeight < dist[nextNode])
            {
                dist[nextNode] = curWeight + nextWeight;
                pq.push({ nextNode,dist[nextNode] });
                parents[nextNode] = curNode;
            }
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        if (i == start) continue;
 
        int child = i;
        int parent = parents[child];
 
        while (1)
        {
            if (parent == start)
            {
                answer[start][i] = child;
                break;
            }
            
            child = parent;
            parent = parents[parent];
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b >> c;
        graph[a].push_back({ b,c });
        graph[b].push_back({ a,c });
    }
 
    for (int i = 1; i <= n; ++i)
    {
        dij(i);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (i == j) printf("- ");
            else printf("%d ", answer[i][j]);
        }
        printf("\n");
    }
}
 

다른 정점으로 최단거리를 갈때 만나는 '첫정점'을 알아야 하는 문제.

처음은 다익스트라로 풀었다. 각정점을 기준으로 다익스트라를 수행할 때, 최단거리를 업데이트할 때 정점들의 부모를 다 저장 후, 반복문이 끝나면 재귀돌려서 시작정점을 찾았을 때의 자식정점을 정답에 업데이트해주는 방식으로 했다.

 

통과는 했는데, 사실 마지막에 재귀를 돌려야하는게 뭔가 마음에 들지 않았다.

그냥 다익로직 수행도중에 전부 다 저장하는 방법은 없는가? 라는 생각이 들어서 다른사람 풀이들을 찾아봤는데 있었다..!

보고나서야 생각이 드는건데, 충분히 가능한 방법이긴 했었다...

 

struct Node
{
    int node;
    int weight;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.weight < b.weight;
    }
};
 
int n, m, a, b, c;
vector<vector<Node>> graph(201);
int answer[201][201];
int dist[201] = { 0 };
 
void dij(int start)
{
    memset(dist, 0x3f, sizeof(dist));
 
    dist[start] = 0;
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ start,0 });
 
    while (!pq.empty())
    {
        int curNode = pq.top().node;
        int curWeight = pq.top().weight;
        pq.pop();
 
        if (dist[curNode] < curWeight) continue;
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            int nextWeight = graph[curNode][i].weight;
 
            if (dist[curNode] + nextWeight < dist[nextNode])
            {
                dist[nextNode] = dist[curNode] + nextWeight;
                pq.push({ nextNode,dist[nextNode] });
                
                if (curNode == start) answer[start][nextNode] = nextNode;
                else answer[start][nextNode] = answer[start][curNode];
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b >> c;
        graph[a].push_back({ b,c });
        graph[b].push_back({ a,c });
    }
 
    for (int i = 1; i <= n; ++i)
    {
        dij(i);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            /*if (i == j) printf("- ");
            else printf("%d ", answer[i][j]);*/
            if (i == j) cout << "- ";
            else cout << answer[i][j] << ' ';
        }
        cout << endl;
    }
}
 

 

dist에 새로운 최단거리를 업데이트 할 때마다, curNode의 첫정점을 nextNode한테 물려주는 방식이다.

이걸 왜 생각 못했지..?

 

 

 

좀 더 대중적인 풀이방법으로는 플로이드 와샬들을 이용한 걸 알 수 있었다.

방법은 정말 간단했는데, 플로이드와샬에서는 dist에 업데이트할 때 중간에 arr[i][k] + arr[k][j] < arr[i][j]일 경우 값을 업데이트하는데, 이 말은 곧 i에서 j로 갈때 k를 거친다는 의미가 된다.

이때 이 k값이 i에서 j로 최단거리로 이동할때의 첫정점이 된다..!

실제로 많은 풀이들이 이렇게 풀이되어 있고, 시간도 빠르다만...  아마 n값이 작아서 그런 것 같다.

n값이 크면 아마 다익스트라로 필요한만큼만의 로직을 수행하는 방식이 더 빠르지 않을까 생각한다.