궤도

[백준] 1238번 : 파티 본문

💻 현생/⛓ 알고리즘

[백준] 1238번 : 파티

영이오 2021. 5. 11. 13:25

문제

 


풀이

 

처음에는 이 문제가 당연히 플로이드-워셜 문제인 줄 알았다... 실제로 그걸로 풀었더니 맞기도 했고...

근데 다익스트라 문제라는 것이다...!

 

난 이해가 되지 않았다. 다익스트라는 하나의 시작점에서 모든 정점과의 거리를 구하는 SSP 알고리즘인데

이 문제는 모든 사람에 대해 도착지점 하나에 대한 거리를 구해야 하기 때문이다...

굳이 모든 정점에 대해 하나하나 다익스트라를 돌리느니 플로이드-워셜이 낫지 않나 했는데

다익스트라 2번으로 해결할 수 있는 방법이 있었다.

 

jow1025.tistory.com/114

 

[백준 1238] 파티

문제출처: https://www.acmicpc.net/problem/1238 풀이 출발->거쳐서->도착 의 패턴이 보여서 플로이드와샬 알고리즘이 끌리는데, 정점의 최대 갯수가 최대 1000이므로, 시간초과가 날 수 있습니다. (그런데

jow1025.tistory.com

이 분의 풀이를 봤다. 정말 생각도 못한 방법이었다.

 

플로이드-워셜로 푼 코드가 아깝기도 하니 둘 다 올리도록 하겠다.

ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고

ko.wikipedia.org


소스코드 - 플로이드-워셜

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int INF = 1e9;

vector<vector<int>> dist;

void floydWarshall() { //플로이드-워셜
    int size = dist.size();
    for (int i = 1; i < size; i++) {
        for (int j = 1; j < size; j++) {
            for (int k = 1; k < size; k++)
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
        }
    }
}

int main() { //풀리긴 했는데 플로이드-워셜로 푸는 문제가 아니라고 함
    int N, M, X, s, d, w;

    cin >> N >> M >> X;
    dist.assign(N + 1, vector<int>(N + 1, INF));
    for (int i = 1; i <= N; i++) //자기 자신과의 거리는 0
        dist[i][i] = 0;
    for (int i = 0; i < M; i++) { //거리 초기 입력
        cin >> s >> d >> w;
        dist[s][d] = w;
    }
    floydWarshall();
    int max_dist = 0;
    for (int i = 1; i <= N; i++) //i-X-i의 거리 중 최댓값 구하기
        max_dist = max(max_dist, dist[i][X] + dist[X][i]);
    cout << max_dist;
}

플로이드-워셜의 전체 소스코드다.

그냥 반복문을 3번 도는거라 코드 자체는 짧다. dist 배열을 갱신하고 나면

i->X로 가는 dist와 X->i로 가는 dist를 더하며 최댓값을 갱신한다.


소스코드 - 다익스트라

 

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
typedef pair<int, int> pp;
const int INF = 1e9;

vector<int> min_dist; //최단 거리
vector<int> result; //결과

void dijkstra(int start, vector<vector<pp>> graph) {
    priority_queue<pp, vector<pp>, greater<pp>> pq; //min-heap
    int size = graph.size();
    min_dist.assign(size, INF); //최단 거리 초기화

    min_dist[start] = 0; //시작점의 거리는 0
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        int cur_dist = pq.top().first; //시작점부터 cur 까지의 최단 거리
        int cur = pq.top().second; //현재 정점
        pq.pop();

        for (int i = 0; i < graph[cur].size(); i++) { //연결된 정점에 대해
            int new_dist = cur_dist + graph[cur][i].second; //cur을 거쳐서 온 거리
            if (new_dist < min_dist[graph[cur][i].first]) { //이게 현재의 graph[cur][i]의 최단 거리보다 짧다면
                min_dist[graph[cur][i].first] = new_dist; //갱신
                pq.push(make_pair(new_dist, graph[cur][i].first)); //큐에 넣기
            }
        }
    }
}

int main() {
    int N, M, X, s, d, w, max_result = 0;
    vector<vector<pp>> graph; //입력 그래프
    vector<vector<pp>> r_graph; //역방향 그래프

    cin >> N >> M >> X;
    graph.assign(N + 1, vector<pp>(0));
    r_graph.assign(N + 1, vector<pp>(0));
    result.assign(N + 1, 0);
    for (int i = 0; i < M; i++) {
        cin >> s >> d >> w;
        graph[s].push_back(make_pair(d, w));
        r_graph[d].push_back(make_pair(s, w));
    }

    dijkstra(X, graph); //X에서 집으로 돌아감
    for (int i = 1; i <= N; i++)
        result[i] = min_dist[i];

    dijkstra(X, r_graph); //집에서 X로 감
    for (int i = 1; i <= N; i++) {
        result[i] += min_dist[i];
        max_result = max(max_result, result[i]); //최댓값 갱신
    }
    cout << max_result;
}

다익스트라의 전체 소스코드다.

 

    vector<vector<pp>> graph; //입력 그래프
    vector<vector<pp>> r_graph; //역방향 그래프

먼저 그래프를 2개 만들고

 

    for (int i = 0; i < M; i++) {
        cin >> s >> d >> w;
        graph[s].push_back(make_pair(d, w));
        r_graph[d].push_back(make_pair(s, w));
    }

연결 관계를 입력한다.

 

    dijkstra(X, graph); //X에서 집으로 돌아감
    for (int i = 1; i <= N; i++)
        result[i] = min_dist[i];

    dijkstra(X, r_graph); //집에서 X로 감
    for (int i = 1; i <= N; i++) {
        result[i] += min_dist[i];
        max_result = max(max_result, result[i]); //최댓값 갱신
    }

그리고 X에서 집으로 돌아가는 경로와 집에서 X로 가는 경로를 구해서 더하는데

 

void dijkstra(int start, vector<vector<pp>> graph) {
    priority_queue<pp, vector<pp>, greater<pp>> pq; //min-heap
    int size = graph.size();
    min_dist.assign(size, INF); //최단 거리 초기화

    min_dist[start] = 0; //시작점의 거리는 0
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        int cur_dist = pq.top().first; //시작점부터 cur 까지의 최단 거리
        int cur = pq.top().second; //현재 정점
        pq.pop();

        for (int i = 0; i < graph[cur].size(); i++) { //연결된 정점에 대해
            int new_dist = cur_dist + graph[cur][i].second; //cur을 거쳐서 온 거리
            if (new_dist < min_dist[graph[cur][i].first]) { //이게 현재의 graph[cur][i]의 최단 거리보다 짧다면
                min_dist[graph[cur][i].first] = new_dist; //갱신
                pq.push(make_pair(new_dist, graph[cur][i].first)); //큐에 넣기
            }
        }
    }
}

코드는 그냥 평범한 다익스트라다.

 

myunji.tistory.com/344

 

[백준] 1753번 : 최단경로

문제 풀이 TMI 난 사실 다익스트라 알고리즘에 트라우마가 있다. 바로 지금보다도 훨씬 아무것도 모르던 2학년 2학기 시절 라이브러리 하나 없이 다익스트라 알고리즘을 구현해야 했던 것이다.

myunji.tistory.com

여기 있는 코드와 유사한데

생각해보니 왜 visited 변수를 넣었는지 모르겠다.

당연히 이미 방문한 노드면 최단 경로가 갱신되지 않을테니 굳이 넣을 필요가 없는데...암튼 그래서 그 부분은 뺐다.

Comments