[python3] 1129. Shortest Path with Alternating Colors

풀이 일자: 23.02.11 ~ 14 

난이도: [Medium]

분류: [BFS, Graph]

문제 내용

n이 주어지고 이를 통해 0 ~ n-1로 각각 라벨링되어있는 노드가 있다고 생각하면 edge가 red인 것과 blue인 것이 존재하며 현재 이루고 있는 graph가 directed graph라고 했을 때 answer[i]이라는 곳에는 0에서 i번째 노드로 갈 때 제일 최단의 길이를 넣어서 리턴하는 문제. ( 단 빨간색과 파란색 edge를 번갈아가며 이동하도록 해야함)

 

문제 해결 흐름

1. 전체적으로는 shortest path 알고리즘을 사용하면 되는 것으로 보이나 우선 directed graph이므로 일단 다익스트라 알고리즘은 사용할 수 없다.

→ 그럼 이를 대체할 알고리즘은 현재 0에서 각 노드로의 최소 거리를 찾는거니까 BFS가 적당하겠다라는 생각을 할 수 있다.

 

# TLE Solution으로 기본적인 TC 통과는 가능하나 n이나 Edges가 많은 경우 TLE가 발생

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        ans = [-1 for i in range(n)];
        
        red = dict();    //red, blue를 dictionary로 관리
        blue = dict();
        
        for edge in redEdges:
            fnode = edge[0];
            lnode = edge[1];

            if fnode not in red:
                red[fnode] = list();
            red[fnode].append(lnode);

        for edge in (blueEdges):
            fnode = edge[0];
            lnode = edge[1];

            if fnode not in blue:
                blue[fnode] = list();
            blue[fnode].append(lnode);

        q = deque([[0,'a',0,[]]]);

        while(1):
            node = q.pop();
            num = node[0]; prevColor = node[1]; depth = node[2]; visited = node[3];

            if ans[num] == -1:   // 현재 num이 -1이라면 depth를 넣는다.
                ans[num] = depth;

            if prevColor == 'a': // 시작점 이라면 
                if num in red:
                    for n in red[num]:
                        if [1, num, n] not in visited:
                            tmp = [[1, num, n]];
                            q.appendleft([n, 'r', depth + 1, tmp]);
                if num in blue:
                    for n in blue[num]:
                        if [2, num, n] not in visited:
                            tmp = [[2, num, n]];
                            q.appendleft([n, 'b', depth + 1, tmp]);
            elif prevColor == 'r':  // 이전이 빨간 edge였다면 
                if num in blue:
                    for n in blue[num]:
                        if [2, num, n] not in visited:
                            tmp = [[2, num, n]] + visited;
                            q.appendleft([n, 'b', depth + 1, tmp]);
            else:                    // 이전이 파란 edge였다면
                if num in red:
                    for n in red[num]:
                        if [1, num, n] not in visited:
                            tmp = [[1, num, n]] + visited;
                            q.appendleft([n, 'r', depth + 1, tmp]);
            if (len(q) == 0):         // queue가 비면 break
                break;
        
        return ans;

[고민했지만 해결되지 않은 점]

1. red와 blue edge에 대한 처리

=> 명백하게 다르고 문제에서도 신경써서 처리해야하고 앞으로 방문할 edge를 검색하기 위해서는 시작점을 key로 하는 각각의 dictionary를 만들자고 생각했다.

=> 하지만 내 의도와는 다르게 어차피 for문으로 key탐색을 해야했고 그 내부의 값(목적지 값을 담은 배열)을 탐색하기 위해 for문을 돌려야 했다.

 

2. 방문했던 edge에 대한 처리..

=> BFS를 하기 위해서는 기준 노드(0)를 잡고 이를 바탕으로 인접한 노드로 빨간색 edge와 파란색 edge를 번갈아가며 depth가 깊어질 텐데 parent node에서 이전에 방문한 길에 대한 정보를 가지고 있어야 빨리 끝난다.

why? 방문한 길을 또다시 반복한다는 것은 뭔가 계속해서 loop가 돌아간다는 의미이다. 같은 노드를 재방문하는 건 문제 없지만 방문했던 edge를 재방문하는게 문제

=> 그래서 이를 처리하기 위해 queue에 넣을 때 방문한 노드의 정보를 넣었는데 방문한 노드의 정보를 알기 위해 또 선형 탐색이 들어가면서 TLE의 주 요인이 되고 있다. 

 

다른 해결 방식( Official Solution Java -> python으로 변경 )

1. 고민했던 red, blue의 문제는 dictionary의 value부분에 색 정보를 추가하는 것으로 해결할 수 있다.

2. 방문에 대한 정보는 2*n크기의 행렬을 만들어 방문했던 node와 색을 통해 정보를 저장한다.

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        adj = dict();   # edges의 모든 정보를  startNode: [[endNode, color], ..] 형태로 저장

        for edge in redEdges:
            if edge[0] not in adj:
                adj[edge[0]] = list();
            adj[edge[0]].append([edge[1], 0]);

        for edge in blueEdges:
            if edge[0] not in adj:
                adj[edge[0]] = list();
            adj[edge[0]].append([edge[1], 1]);

        ans = [-1 for i in range(n)];
        visit = [[False, False] for i in range(n)]; # row는 node의 label된 수 col은 edge색을 의미( 어떤 색의 edge로 도착했는지를 저장)
        q = deque();

        q.appendleft([0, 0, -1]);  # [node의 label된 수, 깊이, 이전 색]
        ans[0] = 0;				   # 0은 안움직여도 되니까 0으로 놓고
        visit[0][1] = visit[0][0] = True;  # 0으로 도착하는 blue red edge는 다 사용했다.


        while(len(q) != 0):
            ele = q.pop();
            node = ele[0]; depth = ele[1]; prevColor = ele[2];

            if(node not in adj.keys()): # 주변 노드가 없으면 끝..
                continue;

            for nei in adj[node]:
                num = nei[0]; color = nei[1];

                if((not visit[num][color]) and (color != prevColor)): #이전에 이번 색 edge로 node에 도착하지 않았고 이전 색과 다르다면
                    if (ans[num] == -1):            # ans가 -1이면 1+depth의 최소 distance가 저장
                        ans[num] = 1 + depth;
                    visit[num][color] = True;       # 특정 color의 edge로 num노드에 도착했음을 체크
                    q.appendleft([num, 1 + depth, color]); # 도착점을 queue에 다시 넣음
        return ans;

=> 고민했던 거에 비해 공식 solution을 확인해보니 생각보다 간단하게 해결한 것으로 보인다. 몇 일 뒤에 다시 풀어봐야겠다.

 

Time Complexity: O(N + e)

e개의 edge에 대한 for문이 돌아가고 있고 N개의 node에 대한 돌아가고 있기에 그 둘의 합만큼의 Time Complexity가 나온다.

 

Space Complexity: O(N + e)

Space Complexity의 경우에도 주변에 대한 정보를 가지고 있는 adj와 답을 저장하는 ans배열을 사용하기에 그 둘의 합만큼 나오게 된다.

 

문제 링크

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

Shortest Path with Alternating Colors - LeetCode