[프로그래머스] 배달

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

그래프의 최단 거리를 계산해서 해결하는 문제이다. 따라서 최단 경로 알고리즘을 사용하면 해결할 수 있을 것으로 보이는데, 해당 문제에서 N이 최대 50이므로 간단한 플로이드-와샬 알고리즘을 사용해서 해결했다. 이 문제에서 플로이드-와샬 알고리즘을 사용할 때 주의할 점은 a에서 b로 가는 경로가 여러 개일 수 있다는 점이다. 따라서 인접 배열을 만들 때, 해당 경로에 대한 최솟값으로 만들어줘야한다.

코드

C++

#include <vector>
#include <algorithm>
#define MAX 987654321
using namespace std;

int solution(int N, vector<vector<int> > road, int K) {
    vector<vector<int>> adj(N + 1, vector<int>(N + 1, MAX));
    for (vector<int> r : road) {
        int a = r[0], b = r[1], c = r[2];
        adj[a][b] = min(adj[a][b], c);
        adj[b][a] = min(adj[b][a], c);
    }

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (adj[i][k] != MAX && adj[k][j] != MAX) {
                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
                }
            }
        }
    }
    int answer = 1;
    for (int i = 2; i <= N; i++)
        if (adj[1][i] <= K) answer++;
    return answer;
}

Java

class Solution {
    static int MAX = Integer.MAX_VALUE;

    public int solution(int N, int[][] road, int K) {
        int[][] adj = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) adj[i][j] = MAX;
        for (int[] r : road) {
            int a = r[0], b = r[1], c = r[2];
            adj[a][b] = Integer.min(adj[a][b], c);
            adj[b][a] = Integer.min(adj[b][a], c);
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j) continue;
                    if (adj[i][k] != MAX && adj[k][j] != MAX) {
                        adj[i][j] = Integer.min(adj[i][j], adj[i][k] + adj[k][j]);
                    }
                }
            }
        }

        int answer = 1;
        for (int i = 2; i <= N; i++)
            if (adj[1][i] <= K)
                answer++;
        return answer;
    }
}