[Algorithm]Baekjoon 1238번 :: 파티

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

1238번: 파티

 

#define MAX_NUM 0x3f3f3f3f
 
int n, m, x;
int a, b, c;
int adjMatrix[1001][1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
 
    cin >> n >> m >> x;
 
    memset(adjMatrix, 0x3f, sizeof(adjMatrix));
 
    for (int i = 1; i <= n; i++)
    {
        adjMatrix[i][i] = 0;
    }
 
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
 
        adjMatrix[a][b] = c;
    }
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            if (adjMatrix[i][k] != MAX_NUM)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (adjMatrix[i][k] + adjMatrix[k][j] < adjMatrix[i][j])
                    {
                        adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                    }
                }
            }
        }
    }
 
    int result = 0;
 
    for (int i = 1; i <= n; i++)
    {
        result = max(result, adjMatrix[i][x] + adjMatrix[x][i]);
    }
 
    cout << result;
}

 

먼저 플로이드와샬로 풀어봤다. 풀리긴 한다.다만 당연히 성능이 좋지 않다.

360ms가 나왔는데, 아마 조금만 정점과 간선개수가 많아지면 시간초과가 날 것이다.

다익스트라로 다시 접근해봐야 한다.

단순 시간복잡도 계산을 하더라도 다익스트라로 하는게 더 빠르긴 했을 것 같다.

 

이 문제같은 경우 버텍스 최대개수는 1000개, 간선개수는 10000개이다.

플로이드와샬은 v^3이니까 1000,000,000이 나온다.

 

다익스트라로 할 경우,  각 버텍스 기준으로 1번씩 돌린다면 

총 1000번의 다익스트라를 수행한다.

한번의 수행에 ElogV니까 1000 * 10000 * log1000 정도? 된다. 1000이면 거의 2의 10승이니까 log 1000이면 10이고.. 

그러면 1000 * 10000 * 10 이니까 대충 1억정도 된다.

대충 계산해도 플로이드와샬보단 훨씬 빠르다.

 

아래는 다익스트라로 푼 코드. (n번의 다익스트라)

 

struct Node
{
    int node;
    int distance;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.distance > b.distance;
    }
};
 
int n, m, x, a, b, c;
int destArr[1001];
vector<vector<Node>> graph(1001);
 
int getShortestDistance(int start, int end)
{
    int dist[1001];
    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 curDistance = pq.top().distance;
        pq.pop();
 
        if (dist[curNode] < curDistance) continue;
 
        for (int i = 0; i < graph[curNode].size(); i++)
        {
            int nextNode = graph[curNode][i].node;
            int nextDistance = graph[curNode][i].distance + curDistance;
 
            if (nextDistance < dist[nextNode])
            {
                dist[nextNode] = nextDistance;
                pq.push({ nextNode,dist[nextNode] });
            }
        }
    }
 
    if (start == x)
    {
        memcpy(destArr, dist, sizeof(dist));
    }
 
    return dist[end];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> x;
 
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
 
        graph[a].push_back({ b,c });
    }
 
    getShortestDistance(x, 0);
 
    int result = 0;
 
    for (int i = 1; i <= n; i++)
    {
        if (i == x) continue;
 
        int toDest = getShortestDistance(i, x);
        int toStart = destArr[i];
 
        result = max(result, toDest + toStart);
    }
 
    cout << result;
}

 

근데 버텍스개수가 정말 많다면 어떻게 될까? 문제에 따라 다르겠지만, 이번 문제에서라면 버텍스개수만큼 다익스트라를 수행해야하기때문에 생각보다 시간이 꽤 걸린다.

애초에 버텍스개수만큼 다익스트라를 수행하는 이유로는, 각 정점에서 목적지까지의 최단거리가 필요하기 때문이다.

각 정점에서 목적지 외의 정점에 가는 최단거리는 전혀 필요가 없다.

알아본 결과, 그래프의 간선정보를 역으로 입력받아서 다익스트라를 수행한다면 다른 노드에서 기준으로 삼은 노드(목적지)까지의 최단거리를 구할 수 있다고 한다. (한번만 수행해서)

 

struct Node
{
    int node;
    int distance;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.distance > b.distance;
    }
};
 
int n, m, dest, a, b, c;
vector<vector<Node>> graph[2];
int dist[2][1001] = { 0 };
 
void dijkstra(int index)
{
    memset(dist[index], 0x3f, sizeof(dist[index]));
    dist[index][dest] = 0;
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ dest,0 });
 
    while (!pq.empty())
    {
        int curNode = pq.top().node;
        int curDistance = pq.top().distance;
        pq.pop();
 
        if (dist[index][curNode] < curDistance) continue;
 
        for (int i = 0; i < graph[index][curNode].size(); i++)
        {
            int nextNode = graph[index][curNode][i].node;
            int nextDistance = graph[index][curNode][i].distance + curDistance;
 
            if (nextDistance < dist[index][nextNode])
            {
                dist[index][nextNode] = nextDistance;
                pq.push({ nextNode,nextDistance });
            }
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> dest;
 
    graph[0].resize(n + 1); // 목적지 -> 각 정점 최단거리용 그래프
    graph[1].resize(n + 1); // 각 정점 -> 목적지 최단거리용 그래프. 간선을 역으로 입력받는다.
 
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
 
        graph[0][a].push_back({ b,c });
        graph[1][b].push_back({ a,c });
    }
 
    dijkstra(0);
    dijkstra(1);
    
    int result = 0;
 
    for (int i = 1; i <= n; i++)
    {
        result = max(result, dist[0][i] + dist[1][i]);
    }
 
    cout << result;
}

 

다익스트라코드 메인로직은 똑같다. 그리고 성능차이는 하늘과 땅차이다.

 

 

아래에서부터 순서대로 플로이드와샬, 다익스트라(n번 수행), 다익스트라(간선정보 역이용)이다.

각각의 로직마다 수행시간이 정말 많이 차이난다.

 

'왜 간선의 정보를 역으로 받아서 다익스트라를 수행하면 다른 노드에서 기준노드까지의 최단거리가 업데이트가 되는가?' 에 대해서는 나도 바로 이해가 되지는 않았는데, 직접 이미지랑 코드를 보면서 생각하니까 얼추 알 수 있긴 했다.

역으로 입력받더라도 로직은 비슷하다는걸 생각하면 느낌이 조금 온다.