[Programmers] 배달

 

 

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

프로그래머스

 

---

 

문제 해결 과정

착안

1번 마을에서부터 시작하여, 1, 2, $\cdots, N$ 번 마을까지의 최단 경로를 모두 구하여 $K$ 시간보다 적게 걸리는 마을의 수를 카운트하여 문제를 해결하기 위해 플로이드-워셜(Floyd-Warshall) 알고리즘을 활용하여 문제를 해결하고자 하였다.

 

구현

$i, j \space (1 \le i, j \le N)$ 번 마을 사이의 최단 경로로 이동할 때의 가중치의 합을 저장할 배열 Towns[$i$][$j$]을 선언하고

• $i = j$ 인 경우: 0으로 초기화
• $i != j$인 경우: 적당히 큰 값으로 초기화(간선 정보로 주어지는 값보다 항상 큰 값)

한 다음, 주어지는 간선 정보를 토대로 Towns[$i$][$j$] 배열에 값을 입력하였다. 이때 두 마을 사이의 경로가 2 개 이상 주어질 수 있기 때문에 가장 가까운 경로로 이동하는 경우로 갱신하여 저장하였으며, 이후 삼중 반복문의 형태로 플로이드-워셜 알고리즘을 구현하여 문제를 해결할 수 있었다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>
using namespace std;

int Towns[51][51];

int solution(int N, vector<vector<int>> road, int K)
{
    int answer = 0;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (i != j)
                Towns[i][j] = 99999999;
    
    for (vector<int> r : road)
        if (Towns[r[0]][r[1]] > r[2])
        {
            Towns[r[0]][r[1]] = r[2];    
            Towns[r[1]][r[0]] = r[2];
        }
    
    for (int w = 1; w <= N; w++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
            {
                int dist = Towns[i][w] + Towns[w][j];
                if (Towns[i][j] > dist)
                    Towns[i][j] = dist;
            }

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

 

실행 결과