[Lv.2] 배달 [프로그래머스_코딩테스트] [다익스트라, 그래프] [40분] [Summer/Winter Coding(~2018)]

🔍 문제 요약

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

프로그래머스

N개의 마을이 주어지고 마을에서 마을로 이동할 때 걸리는 시간 데이터 road(시작 마을, 끝마을, 걸리는 시간)가 주어질 때 K 시간 이하로 배달할 수 있는 마을의 수를 구하기

🧠 나의 접근 방식과 시행착오

시간 1시간 넘게 잡아 먹었다... 그러고 틀린 문제. BFS로 시도했다가 DFS로 바꿨는데 75프로 테스트 케이스 통과하고 25프로는 틀렸던 문제. 뭔가 어디선가 문제가 생긴 듯 한데.. DFS를 활용하는 방법도 틀린 건지도 모르겠다. 일단 풀이 피드백에서 좀 더 알아볼 예정.

using System;
using System.Collections.Generic;

public class Solution
{
    public struct Node
    {
        public int End { get; set; }
        
        public int Time { get; set; }

        public Node(int end, int time)
        {
            End = end;
            Time = time;
        }
    }
    
    Dictionary<int, bool> visitDict = new Dictionary<int, bool>();
    List<List<Node>> graph = new List<List<Node>>();
    
    /// <summary>
    /// 배달
    /// https://school.programmers.co.kr/learn/courses/30/lessons/12978
    /// </summary>
    public int solution(int N, int[,] road, int K)
    {
        // 1번 마을에서 K 시간 이하로 배달이 가능한 곳 개수 구하기
        // road는 (마을 번호 a, 마을 번호 b, 걸리는 시간)으로 구성
        
        // 풀이
        // 그래프를 표시하기 위해서 리스트를 연결
        // List의 인덱스를 번호로 보자.
        graph.Clear();
        visitDict.Clear();

        for (int i = 0; i <= N; i++)
        {
            graph.Add(new List<Node>());
        }

        for (int i = 0; i < road.GetLength(0); i++)
        {
            int start = road[i, 0];
            int end = road[i, 1];
            int time = road[i, 2];
            
            graph[start].Add(new Node(end, time));
            graph[end].Add(new Node(start, time));
        }
        
        int remainTime = K;
        // 1번 마을에서 시작했으니 1번 마을은 시간이 0이라 무조건 1에서 시작
        var visitSpotDict = new Dictionary<int, bool>();
        visitSpotDict.Add(1, true);
        
        for (int i = 0; i < graph[1].Count; i++)
        {
            visitDict.Clear();
            visitDict.Add(1, true);

            DFS(visitDict, graph[1][i], remainTime, graph, visitSpotDict);
        }
     
        return visitSpotDict.Count;
    }

    private void DFS(Dictionary<int, bool> visited, Node node, int remainTime, List<List<Node>> graph,
        Dictionary<int, bool> visitSpotDict)
    {
        if (visited.ContainsKey(node.End)) return;
        if (remainTime < node.Time) return;

        remainTime -= node.Time;
        visited.Add(node.End, true);

        if (!visitSpotDict.ContainsKey(node.End))
        {
            visitSpotDict.Add(node.End, true);
        }
        
        var list = graph[node.End];

        for (int i = 0; i < list.Count; i++)
        {
            DFS(visited, list[i], remainTime, graph, visitSpotDict);
        }
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        int n0 = 5;
        var road0 = new int[,] {{1,2,1},{2,3,3},{5,2,2},{1,4,2},{5,3,1},{5,4,2 }};
        int k0 = 3;
        var res0 = sl.solution(n0, road0, k0);
        Console.WriteLine(res0);
        
        int n1 = 6;
        var road1 = new int[,]
            { { 1, 2, 1 }, { 1, 3, 2 }, { 2, 3, 2 }, { 3, 4, 3 }, { 3, 5, 2 }, { 3, 5, 3 }, { 5, 6, 1 } };
        int k1 = 4;
        var res1 = sl.solution(n1, road1, k1);
        
        Console.WriteLine(res1);
    }
}

✅ 풀이 코드

문제를 풀 때 DFS로 시도했을 때의 문제점은 Visited에서 긴 시간이 걸렸을 때 체크가 잘못 된 것으로 보인다. 긴 시간으로 한 번 체크를 해버렸으면 다시 못가는 식으로 막아버린 점이 문제. 짧은 경로로 가야 하기에 다익스트라로 해결해야 한다고 함.

using System;
using System.Collections.Generic;

public class Solution
{
    public int solution(int N, int[,] road, int K)
    {
        // 그래프 초기화
        List<(int to, int cost)>[] graph = new List<(int, int)>[N + 1];
        for (int i = 0; i <= N; i++)
            graph[i] = new List<(int, int)>();

        for (int i = 0; i < road.GetLength(0); i++)
        {
            int a = road[i, 0];
            int b = road[i, 1];
            int c = road[i, 2];
            graph[a].Add((b, c));
            graph[b].Add((a, c));
        }

        int[] dist = new int[N + 1];
        for (int i = 0; i <= N; i++)
            dist[i] = int.MaxValue;

        dist[1] = 0;
        var pq = new PriorityQueue<int, int>();
        pq.Enqueue(1, 0);

        while (pq.Count > 0)
        {
            pq.TryDequeue(out int current, out int cost);

            if (cost > dist[current]) continue;

            foreach (var (next, nextCost) in graph[current])
            {
                int totalCost = cost + nextCost;
                if (totalCost < dist[next])
                {
                    dist[next] = totalCost;
                    pq.Enqueue(next, totalCost);
                }
            }
        }

        // K 이하 거리인 마을 수 카운트
        int count = 0;
        for (int i = 1; i <= N; i++)
        {
            if (dist[i] <= K)
                count++;
        }

        return count;
    }
}

🔄 정리

다익스트라 알고리즘에 익숙치 않았어서 헤맸지만 결국 비용을 최소로 해서 이동할 수 있게 우선순위 큐에 넣고 비용일 떨어질 때까지 돌려본다.