<Medium> Shortest Path with Alternating Colors (LeetCode : C#)

https://leetcode.com/problems/shortest-path-with-alternating-colors/

📕 문제 설명

간선이 빨간색 또는 파란색인 방향이 있는 그래프가 있다. 길을 갈때 색을 번갈아 가면서 움직여야 한다. answer[x]에 node 0번에서 x번으로 가는 최단 거리를 담아 반환하기 (못 가는 경우 -1 담기)

redEdges[i] = [a_i, b_i], a_i에서 b_i로 빨간 간선 존재
blueEdges[i] = [u_j, v_j], u_j에서 v_j로 파란 간선 존재

• Input
  노드 개수 n, redEdge 정보, blueEdge 정보
• Output
  0번 노드에서 도달할 수 있으면 최단 거리 담고 아니면 -1 담은 배열 반환

예제

풀이

색을 번갈아서 간선을 타야하기 때문에 색 정보도 저장할 수 있도록 작성하였다.

public class Solution {
    public int[] ShortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<int>[] red = new List<int>[n];
        List<int>[] blue = new List<int>[n];

        for (int i = 0; i < n; i++)
        {
            red[i] = new List<int>();
            blue[i] = new List<int>();
        }
        // 인접 정보 초기화
        foreach (int[] edge in redEdges) red[edge[0]].Add(edge[1]);
        foreach (int[] edge in blueEdges) blue[edge[0]].Add(edge[1]);

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) answer[i] = -1;

        Queue<(int node, bool color)> queue = new Queue<(int node, bool color)>();
        queue.Enqueue((0, true));
        queue.Enqueue((0, false));

        HashSet<(int node, bool color)> visited = new HashSet<(int node, bool color)>();
        visited.Add((0, true));
        visited.Add((0, false));

        int dist = 0;
        while (queue.Count > 0)
        {
            int count = queue.Count;
            for (int i = 0; i < count; i++)
            {
                var (node, color) = queue.Dequeue();
                if (answer[node] == -1) answer[node] = dist; // 처음 도달되는 경우 
                if (color)
                {
                    foreach (int next in red[node]) 
                    {
                        if (!visited.Contains((next, false))) // 인접 노드 + 다른 간선 색 -> 아직 미방문했으면
                        {
                            queue.Enqueue((next, false));
                            visited.Add((next, false));
                        }
                    }
                }
                else
                {
                    foreach (int next in blue[node])
                    {
                        if (!visited.Contains((next, true))) // 인접 노드 + 다른 간선 색 -> 아직 미방문했으면
                        {
                            queue.Enqueue((next, true));
                            visited.Add((next, true));
                        }
                    }
                }
            }
            dist++;
        }

        return answer;   
    }
}

결과