<Lv.3> 부대 복귀 (프로그래머스 : C#)

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

📕 문제 설명

두 지역간 길을 통과하는데 1의 시간이 걸린다. 임무를 수행한 각 부대원은 지도 정보를 이용해 최단시간에 부대에 복귀하고자 한다. 각 부대원들이 위치한 지역에 대해 복귀할 수 있는 최단 시간을 담은 배열 반환하기

• Input
  강철부대가 위치한 총 위치 수, 두 지역 왕복하는 길 정보, 각 부대원이 위치한 서로 다른 지역들, 강철부대의 지역
• Output
  각 부대원들이 위치한 지역에 대해 강철부대로 복귀할 수 있는 최단시간 (복귀 불가능시 -1)

예제

풀이

초반에 source를 기준으로 생각해서 시간 초과가 났다. 생각해보니 dest 기준으로 연결된 부분들 거리를 구해주고 (BFS) 그냥 답에 거리 넣어주면 답이 나온다.

최소 거리를 구하기 위해 distFromDest에 Math.Min으로 갱신해주었고 추가로 source에 있는 숫자인데 dest에서 못 도달하는 경우도 있어서 distFromDest가 초기에 설정한 100001과 같아도 -1로 처리해줬다. (이부분 처리 안하면 테케 5가 통과가 되지 않는다.)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int[] solution(int n, int[,] roads, int[] sources, int destination) {
        int[] answer = new int[sources.Length];
        
        List<int>[] graph = new List<int>[n+1];
        // graph 초기화
        for (int i = 1; i <= n; i++)
        {
            graph[i] = new List<int>();
        }
        for (int i = 0; i < roads.GetLength(0); i++)
        {
            int road1 = roads[i, 0];
            int road2 = roads[i, 1];
            graph[road1].Add(road2);
            graph[road2].Add(road1);
        }
        
        int[] distFromDest = Enumerable.Repeat(100001, n+1).ToArray();
        // dest 기준 BFS로 dist 구하기
        // node Num, curr Dist
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((destination, 0));
        bool[] visited = new bool[n + 1];
        visited[destination] = true;
        distFromDest[destination] = 0;
        
        while (queue.Count >= 1)
        {
            (int currNode, int dist) = queue.Dequeue();
            distFromDest[currNode] = Math.Min(dist, distFromDest[currNode]);
            visited[currNode] = true;
            
            foreach(int adjNode in graph[currNode])
            {
                if (visited[adjNode]) continue;
                queue.Enqueue((adjNode, dist + 1));
            }   
        }
        
        for (int i = 0; i < sources.Length; i++)
        {
            int source = sources[i];
            
            if (graph[source].Count == 0) 
            {
                answer[i] = -1;
                continue;
            }
            
            if (distFromDest[source] == 100001)
            {
                answer[i] = -1;
                continue;
            }
            
            answer[i] = distFromDest[source];
        }
        
        
        return answer;
    }
}

결과