[프로그래머스 C#] Lv.2 배달

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

- 정점 (마을)

- 간선 (마을 간 이동가능 여부)

- 가중치 (간선을 지나가는 데 필요한 이동시간)

 

1번 정점과 특정 거리 이상 떨어져있지 않은 정점의 개수를 구하는 문제 (다익스트라 알고리즘)

- 1번 정점과의 거리를 나타내는 1차원 배열을 선언 ( int[] intArray ) // 최단거리배열

- 최초에 탐색 없이 알 수 있는 정보인 1번 정점부터 탐색을 시작

 - 1번 정점과 이어진 간선을 찾아서 최단거리배열 최소 값을 확인해 갱신

 - 갱신된 정점은 다음 탐색 대상으로 지정하여 탐색 대상이 없을 때까지 순회 

 

다익스트라 알고리즘

- Dynamic Programming (DP : 동적 계획법) 을 활용한 알고리즘

https://godgjwnsgur7.tistory.com/109

[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation

주석 참조

    using System;
    using System.Collections.Generic;

    class Solution
    {
        public int solution(int N, int[,] road, int K)
        {
            int answer = 0;
            var intArray = new int[N + 1]; // 최단거리(최단시간)배열
            var queue = new Queue<int>(); // 탐색대상 큐

            // 초기 값 세팅
            for (int i = 0; i < intArray.Length; i++)
                intArray[i] = K + 1; // K보다 큰 수는 의미가 없으므로

            intArray[1] = 0; // 자기자신과의 거리는 0
            queue.Enqueue(1); // 유일하게 알고 있는 정점부터 탐색

            // 갱신 대상이 없을 때까지 순회
            while (queue.Count > 0)
            {
                int n = queue.Dequeue(); // 갱신 대상 마을 번호

                // 갱신 대상과 연결된 간선을 탐색 (탐색 마을번호 i)
                for (int i = 0; i < road.GetLength(0); i++)
                {
                    int n1 = road[i, 0]; // 1번 마을 번호
                    int n2 = road[i, 1]; // 2번 마을 번호
                    int dir = road[i, 2]; // 1번 마을 <-> 2번 마을

                    // 연결된 간선을 찾았다면 최소 값인지 체크해서 갱신
                    if (n == n1 && intArray[n2] > dir + intArray[n1])
                    {
                        intArray[n2] = dir + intArray[n1];
                        queue.Enqueue(n2); // 갱신되었으므로 탐색 대상
                    }
                    else if (n == n2 && intArray[n1] > dir + intArray[n2])
                    {
                        intArray[n1] = dir + intArray[n2];
                        queue.Enqueue(n1); // 갱신되었으므로 탐색 대상
                    }
                }
            }

            foreach (int num in intArray)
                if (num <= K)
                    answer++;

            return answer;
        }
    }