배달

문제

문제 풀이

using System;
using System.Collections.Generic;

public class Solution
{
    public int solution(int N, int[,] road, int K)
    {
        // 그래프 초기화: 각 마을에 대한 연결 정보
        List<Tuple<int, int>>[] graph = new List<Tuple<int, int>>[N + 1];
        for (int i = 1; i <= N; i++)
        {
            graph[i] = new List<Tuple<int, int>>();
        }

        // 도로 정보로 그래프 채우기 (양방향)
        int roadLength = road.GetLength(0);  // 도로의 개수
        for (int i = 0; i < roadLength; i++)
        {
            int start = road[i, 0];
            int end = road[i, 1];
            int time = road[i, 2];

            // 양방향 도로이므로 양쪽에 정보를 추가
            graph[start].Add(new Tuple<int, int>(end, time));
            graph[end].Add(new Tuple<int, int>(start, time));
        }

        // 다익스트라 알고리즘을 위한 최단 거리 배열 초기화
        int[] dist = new int[N + 1];
        for (int i = 1; i <= N; i++) dist[i] = int.MaxValue;
        dist[1] = 0; // 1번 마을의 거리는 0

        // 방문 여부 체크 배열
        bool[] visited = new bool[N + 1];

        // 다익스트라 알고리즘
        for (int i = 1; i <= N - 1; i++) // N-1번 반복
        {
            // 현재 최소 비용을 가진 마을을 찾음
            int minDist = int.MaxValue;
            int currentVillage = -1;

            // 아직 처리되지 않은 마을 중 최단 거리가 가장 작은 마을을 찾음
            for (int j = 1; j <= N; j++)
            {
                if (!visited[j] && dist[j] < minDist)
                {
                    minDist = dist[j];
                    currentVillage = j;
                }
            }

            // 현재 마을을 방문 처리
            visited[currentVillage] = true;

            // 현재 마을과 연결된 마을들 확인
            foreach (var neighbor in graph[currentVillage])
            {
                int nextVillage = neighbor.Item1;
                int travelTime = neighbor.Item2;

                // 최소 비용으로 갱신
                if (dist[currentVillage] + travelTime < dist[nextVillage])
                {
                    dist[nextVillage] = dist[currentVillage] + travelTime;
                }
            }
        }

        // 배달 가능한 마을 카운트
        int count = 0;
        for (int i = 1; i <= N; i++)
        {
            if (dist[i] <= K) count++;
        }

        return count;
    }
}