[프로그래머스] 12978 : 배달(플로이드,다익스트라 풀이), 다익스트라&플로이드 template

url : https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

다익스트라 또는 플로이드 워셜로 풀 수 있는 문제이다.

플로이드 워셜이 구현이 훨씬 편리하므로 n이 500이하일 경우 플로이드 워셜로 풀면 좋다.

나의 경우에는 다익스트라로 풀었다. + 1211 플로이드 워셜 풀이 추가

 

그래프 문제는 조금만 익숙하지 않아도 어려워지는 것 같다.

하지만 정해진 템플릿에 기반하여 그려보며 풀면 생각보다 쉽게 풀리는 문제이기도 하다.

 

다익스트라 template

#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 최단 거리 테이블 만들기
int d[100001];

void dijkstra(int start) {
    priority_queue<pair<int, int> > pq;
    // 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    pq.push({0, start});
    d[start] = 0;
    while (!pq.empty()) { // 큐가 비어있지 않다면
        // 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        int dist = -pq.top().first; // 현재 노드까지의 비용 
        int now = pq.top().second; // 현재 노드
        pq.pop();
        // 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if (d[now] < dist) continue;
        // 현재 노드와 연결된 다른 인접한 노드들을 확인
        for (int i = 0; i < graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            // 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if (cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push(make_pair(-cost, graph[now][i].first));
            }
        }
    }
}

int main(void) {
    cin >> n >> m >> start;

    // 모든 간선 정보를 입력받기
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph[a].push_back({b, c});
    }

    // 최단 거리 테이블을 모두 무한으로 초기화
    fill(d, d + 100001, INF);
    
    // 다익스트라 알고리즘을 수행
    dijkstra(start);

    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= n; i++) {
        // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if (d[i] == INF) {
            cout << "INFINITY" << '\n';
        }
        // 도달할 수 있는 경우 거리를 출력
        else {
            cout << d[i] << '\n';
        }
    }
}

출처 : https://github.com/ndb796/python-for-coding-test/blob/master/9/2.cpp

 

플로이드 template

#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M)
// 노드의 개수는 최대 500개라고 가정
int n, m;
// 2차원 배열(그래프 표현)를 만들기
int graph[501][501];

int main(void) {
    cin >> n >> m;

    // 최단 거리 테이블을 모두 무한으로 초기화
    fill(&graph[0][0], &graph[0][0]+51*51, INF);


    // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
    for (int a = 1; a <= n; a++) {
        graph[a][a] = 0;
    }

    // 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
    for (int i = 0; i < m; i++) {
        // A에서 B로 가는 비용은 C라고 설정
        int a, b, c;
        cin >> a >> b >> c;
        graph[a][b] = c;
    }
    
    // 점화식에 따라 플로이드 워셜 알고리즘을 수행
    for (int k = 1; k <= n; k++) {
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
            }
        }
    }

    // 수행된 결과를 출력
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
            if (graph[a][b] == INF) {
                cout << "INFINITY" << ' ';
            }
            // 도달할 수 있는 경우 거리를 출력
            else {
                cout << graph[a][b] << ' ';
            }
        }
        cout << '\n';
    }
}

출처: https://github.com/ndb796/python-for-coding-test/blob/master/9/3.cpp

 

 

다익스트라 풀이

#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[51]; // 최대 50개의 마을
// 최단 거리 테이블 만들기
int d[51];


void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //내림차순 큐
    pq.push({0, start});
    d[start] = 0;
    while (!pq.empty()) {
        int dist = pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if (d[now] < dist) continue;
        for (int i = 0; i < graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            if (cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push({cost, graph[now][i].first});
            }
        }
    }
}

int solution(int N, vector<vector<int> > road, int K) {
    // 최단 거리 테이블을 모두 무한으로 초기화
    fill(d, d + 51, INF);

    // 모든 도로 정보를 입력받아 그래프 구성
    for (int i = 0; i < road.size(); i++) {
        // 양방향 도로
        graph[road[i][0]].push_back({road[i][1], road[i][2]});
        graph[road[i][1]].push_back({road[i][0], road[i][2]});
    }

    // 다익스트라 알고리즘을 수행, 시작 노드는 1로 설정
    dijkstra(1);

    int answer = 0;
    // K 시간 이하로 배달이 가능한 마을의 수 계산
    for (int i = 1; i <= N; i++) {
        if (d[i] <= K) answer++;
    }

    return answer;
}

 

 

플로이드-워셜 풀이

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
int graph[51][51];

int solution(int N, vector<vector<int>> road, int K) {
    //1. 초기화 + 입력
    fill(&graph[0][0], &graph[0][0]+51*51, INF);
    for(int i=1;i<=N;i++){
        graph[i][i]=0;
    }
    for(int i=0;i<road.size();i++){
        graph[road[i][0]][road[i][1]]=min(graph[road[i][0]][road[i][1]], road[i][2]);
        graph[road[i][1]][road[i][0]]=min(graph[road[i][1]][road[i][0]], road[i][2]);
    }
    //2. 플로이드 워셜 알고리즘 수행
    for(int k=1;k<=N;k++){
        for(int a=1;a<=N;a++){
            for(int b=1;b<=N;b++){
                graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b]);
            }
        }
    }
    //3. 1번 마을에서 출발하여 K시간 내 도착하는 마을 수 찾기
    int answer = 0;
    for(int i=1;i<=N;i++){
        if(graph[1][i]<=K) answer++;
    }

    return answer;
}