[C++] 백준/BOJ - 21940 : 가운데에서 만나기 (다익스트라 풀이)

---

문제 이해 단계

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

21940번: 가운데에서 만나기

정점과 간선 정보가 주어진다.

각 간선은 단방향으로 주어지고, 간선에는 시간이라는 가중치가 존재한다.

여기서 선택해야 하는 것은 왕복 시간(목적지로 갔다가 다시 돌아오는데 드는 시간)이
가장 많이 드는 사람의 시간을 최소화하는 도시를 선택하는 것이다.

도시의 개수 N과 간선의 개수 M, 그리고 사람 수 K와 각 사람이 사는 도시 정보가 주어진다.

왕복 시간이 가장 많이 드는 사람의 시간을 최소화하는 도시를 출력하고,
만약 여러 개라면 오름차순으로 여러 개를 출력해라.

 

---

문제 접근 단계

일단, 문제에서 바로 알 수 있듯이 그래프 탐색 문제이다.

정점과 간선이 존재하고 각 간선은 시간이라는 가중치가 존재한다.

여기서는 가중치 하나만이 중요한 게 아니라 왕복시간이라고 해서
한 노드에서 시작해서 돌아오는데 걸리는 비용까지 전부 계산해야 한다.

일단 문제에서 요구하는 한 도시에서 다른 도시의 왕복시간을 구하기 위해서는
일단 한 도시에서 다른 도시로, 편도로 가는 비용부터 알아야 한다.

어느 도시가 최대 왕복시간일지 모르기 때문에,
모든 도시에 대해서 계산해줘야 한다.

하지만 직접적으로 연결되어 있지 않은 경우도 있고,
돌아서 가는 경우가 더 비용이 적게 드는 경우도 있다.

그래서 이를 각 도시를 기준으로
다익스트라 알고리즘을 돌려, DP 2차원 배열에 저장하기로 했다.

다익스트라 알고리즘을 통해 한 도시에서 다른 도시로 가는 최단 시간 알 수 있다.
그러므로 반대로 갔던 도시에서 다시 자기 자신에게 오는 최단 시간,
즉 왕복 시간을 알 수 있다.

모든 도시에 대한 왕복 시간에 대한 관계를 구하고 나면,
최대 왕복시간 또한 쉽게 알 수 있고, 답 또한 구할 수 있게 된다.

다익스트라 알고리즘이나 자세한 로직 같은 부분은
코드에서 설명하겠다.

 

---

문제 구현 단계

#define INF 999999

// 한 도시(정점)가 가지고 있는 정보
struct Info{
    int end;
    int cost;
};

// 우선순위 큐 정렬 기준 ->  비용이 가장 낮은 것부터 나옴 
struct compare{
    bool operator()(Info a, Info b){
        return a.cost > b.cost;
    }
};
int N,M;

// dp 테이블 -> dp[a][b] = 도시a에서 b로 가는 최소 비용
int dp[201][201] = {0,};
vector<Info> v[201];


// 다익스트라(매개변수 기준 도시)
void dijkstra(int n){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    dp[n][n] = 0; // 출발 도시 = 0
    q.push({0,n});

    while(!q.empty()){
        int x = q.top().second; // 출발 도시
        int time = q.top().first; // 현재 사용 시간
        q.pop();

        // 갈 수 있는 도착 도시
        for(int i = 0; i < v[x].size(); i++){
            int nx = v[x][i].end; // 도착 도시
            int nextTime = v[x][i].cost+time; // 현재 시간 + 가는데 드는 비용
            if(nextTime < dp[n][nx]){
                // 해당 dp 테이블에 저장되어 있는 최소 시간과 비교
                dp[n][nx] = nextTime; // dp 테이블 값보다 작다면 갱신
                q.push({nextTime,nx});
            }
        }
    }
}

우선순위큐의 정렬기준을 세워준 부분과 다익스트라 알고리즘 부분이다. 

정렬기준은 시간을 기준으로,
뽑았을 때 시간이 적은 것부터 나오도록 오름차순 정렬로 해놨다.

dp테이블은 2차원으로 선언해 뒀다.
dp [a][b] = 도시 a에서 도시 b까지 가는데 걸리는 최소 비용이라는 뜻이다.

다익스트라 부분은 공식화되어 있는 부분이기 때문에 자세한 것은 아래에 링크를 걸어두겠다.

이 링크는 내가 다익스트라를 이해하는데 가장 도움이 많이 된 동빈나 님의 설명 링크이다.
https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

 int num;
    cin >> num;
    vector<int> friends(num);
    for(int i = 0; i < num; i++) cin >> friends[i];

    vector<int> answer;
    int distance = 999999;
    for(int i = 1; i <= N; i++){
        int place = i;
        int tmp = 0;
        for(int j = 0; j < num; j++){
            
            int val = dp[place][friends[j]] + dp[friends[j]][place];
            tmp = max(tmp,val);
        }
        if(distance > tmp){
            answer.clear();
            answer.push_back(i);
            distance = tmp;
        }
        else if(distance == tmp) answer.push_back(i);
    }
    for(auto it : answer) cout << it << " ";

해당 코드는 다익스트라를 통해 만들어둔 2차 dp 테이블을 통해 도시를 정하는 부분이다.

한 도시씩 순회하면서,해당 도시를 약속지점으로 가정한다.
그 후 친구들의 원래 위치에서 그곳으로의 왕복시간을 구하여 그 중 가장 큰 값을 구한다.

그 걸 모든 도시에 대해 반복하여 가장 작은 값을 구한다.
그 값이 정답이 되는 것이다.

중복이 될 수 있으니 vector로 선언해 둬 여러 개 담을 수 있도록 한다.

 

---

시행착오

다익스트라 알고리즘으로 풀었는데, 사람들은 플루이드 워셜로 풀면 더 쉽게 풀 수 있다고 한다.
어쩐지 이렇게 푸니까 구현문제 같고 시간이 오래 걸리더라..

그래도 이 문제는 인터넷 참고 없이 순수하게 푼 문제라서 기분이 좋다.
오랜만에 이렇게 푸니까 자신감이 차오르는 것 같다.

그래도 플로이드 워셜 알고리즘을 공부하고
나중에 정리해봐야 할 것 같다.

https://toss.me/howudong

howudong님에게 보내주세요