[프로그래머스 C#] Lv.3 부대 복귀

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

프로그래머스

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

주어진 병사들의 위치에서 도착지(강철부대)까지의 최단거리를 구하는 문제

- 어느 지역에 있는 병사라도 결국 도착지로 이동해야 함

 -> 도착지를 기준으로 갈 수 있는 모든 지역에 대한 최단 거리를 구함

- 정점과 간선으로 봤을 때, 가중치는 무조건 1

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public int[] solution(int n, int[,] roads, int[] sources, int destination)
        {
            int[] answer = new int[sources.Length];
            var intArray = new int[n]; // 최단거리 배열 (갈 수 없는 지역 : -1)
            var dict = new Dictionary<int, List<int>>(); // 간선 그래프
            
            // 초기 값 세팅
            for (int i = 1; i <= n; i++)
            {
                intArray[i] = -1; // 세팅 전
                dict.Add(i, new List<int>());
            }
            
            // 간선 그래프 세팅
            for (int i = 0; i < roads.GetLength(0); i++)
            {
                dict[roads[i, 0]].Add(roads[i, 1]);
                dict[roads[i, 1]].Add(roads[i, 0]);
            }
            
            // 부대위치로부터 각 지역에 가는 최단 거리를 구함
            var queue = new Queue<int>();
            queue.Enqueue(destination);
            intArray[destination] = 0;
            
            // BFS 탐색
            while (queue.Count > 0)
            {
                int currNum = queue.Dequeue(); // 현재 지역

                foreach (int moveNum in dict[currNum]) // 이동 지역
                {
                    // 최단 거리가 입력되지 않은 지역이라면
                    if (intArray[moveNum] == -1)
                    {
                        // 최단 거리 세팅 (가중치는 무조건 1)
                        intArray[moveNum] = intArray[currNum] + 1;
                        queue.Enqueue(moveNum); // 탐색 대상
                    }
                }
            }

            // 병사 위치에 따라 부대 복귀하는 최단 거리 세팅
            for (int i = 0; i < sources.Length; i++)
                answer[i] = intArray[sources[i]];

            return answer;
        }
    }