C# 배달 - 다익스트라 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/12978

 

 

나의 풀이

public int solution(int N, int[,] road, int K)
{
    // 거리 초기화
    int[,] map = new int[N, N];
    for(int i = 0; i < N; ++i)
    {
        for(int k = 0; k < N; ++k)
            map[i, k] = int.MaxValue;
    }
    for(int i = 0; i < road.GetLength(0); ++i)
    {
        int a = road[i, 0] - 1;
        int b = road[i, 1] - 1;
        int dist = road[i, 2];

        if(dist < map[a, b])
            map[a, b] = map[b, a] = dist;
    }

    // 경로 찾기 전 초기화
    var times = new int[N];
    var visit = new bool[N];
    for(int i = 0; i < N; ++i)
        times[i] = map[0, i];

    times[0] = 0; 
    visit[0] = true; 

    // 경로 찾기. 최초 시작위치에서 한개씩 확정짓기 때문에 시작노드를 제외한 N-1
    for(int repeat = 0; repeat < N - 1; ++repeat)
    {
        int now = -1;
        int min = int.MaxValue;
        // 아직 방문하지 않은 노드 중 최단거리 찾기
        for(int j = 0; j < N; ++j)
        {
            if(visit[j]) continue;
            if(times[j] == int.MaxValue) continue;
            if(times[j] >= min) continue;

            min = times[j];
            now = j;
        }

        visit[now] = true;

        for(int k = 0; k < N; ++k)
        {
            if(visit[k]) continue;
            if(map[now, k] == int.MaxValue) continue;

            // 직접 가는거보다 다른경로를 거쳐서 도달하는게 더 빠르면
            if(times[k] > times[now] + map[now, k]) 
                times[k] = times[now] + map[now, k];
        }
    }

    return times.Count(c => c <= K);
}

다익스트라를 활용하여 모든 경로를 완전탐색하는 문제.

매 상황에서 방문하지 않은 비용이 가장 적은 노드를 선택하는 그리디 알고리즘이 더해졌다.

한 단계마다 가장 가까운 노드 now를 지정하고,

다른 모든 노드들에 도달하기 위해 노드 now를 경유해서 도달하면 더 빨라지는 경우 값을 고친다. 

 

다익스트라 말고도 BFS나 플로이드-워셜로도 풀 수 있다고 한다.

 

다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구한다. (1차원 배열)

플로이드-워셜 알고리즘은 모든 노드 간 최단 경로를 구한다. (2차원 행렬)

 

 

풀이 2

public int solution(int N, int[,] road, int K)
{
    int answer = 0;
    int[] path = Enumerable.Repeat(int.MaxValue, N + 1).ToArray(); // 1번부터 시작하니 한개를 추가함
    path[1] = 0; // 시작지점 0

    for(int repeat = 0; repeat < N - 1; ++repeat)
    {
        for(int target = 1; target < N + 1; ++target)
        {
            for(int r = 0; r < road.GetLength(0); ++r)
            {
                int a = road[r, 0];
                int b = road[r, 1];
                int dist = road[r, 2];

                // 더할 때 int.MaxValue라면 오버플로우 발생
                if(a == target && path[a] != int.MaxValue)
                {
                    // 시작점 -> b 의 거리 보다 시작점 -> a -> b 의 거리가 더 짧다면 고침.
                    path[b] = Math.Min(path[b], path[a] + dist);
                }
                else if(b == target && path[b] != int.MaxValue)
                {
                    // 시작점 -> a 의 거리 보다 시작점 -> b -> a 의 거리가 더 짧다면 고침.
                    path[a] = Math.Min(path[a], path[b] + dist);
                }
            }
        }
    }

    return path.Count(c => c <= K);
}

역시 다익스트라지만 훨씬 더 간소화된 버전.

수도코드 수준으로 기본적인 부분만 남겼다.