Shortest Path with Alternating Colors: หาเส้นทางสั้นสุดสลับสี

โจทย์

Directed graph โหนด 0..n-1 Edge มีสี แดง (red) หรือ น้ำเงิน (blue) หา shortest path จากโหนด 0 ไปทุกโหนด โดย สี edge ต้องสลับกัน (red→blue→red...)

คืน array answer ขนาด n: answer[X] = ความยาว shortest alternating path 0→X (หรือ -1 ถ้าไม่มี)

อัลกอริทึม: BFS บน State Graph (Node, Color)

State = (node, last_color) โดย last_color = สีของ edge ที่ใช้มาถึง node นี้

• เริ่มจาก (0, None) (ยังไม่มีสี)
• จาก state (u, last_color) ไปได้เฉพาะ edge สีตรงข้ามกับ last_color
• BFS ให้ shortest path แบบ unweighted graph
• รัน 2 รอบ: เริ่มด้วย red edge และ เริ่มด้วย blue edge (หรือรวมใน BFS เดียว)

การติดตั้ง (Python Implementation)

from collections import deque

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: list[list[int]], blue_edges: list[list[int]]) -> list[int]:
        # Build adjacency lists by color
        red_adj = [[] for _ in range(n)]
        blue_adj = [[] for _ in range(n)]
        for u, v in red_edges:
            red_adj[u].append(v)
        for u, v in blue_edges:
            blue_adj[u].append(v)
        
        # dist[node][color] = shortest distance to node ending with color
        # color: 0 = red, 1 = blue, 2 = none (start)
        INF = float('inf')
        dist = [[INF, INF] for _ in range(n)]
        dist[0] = [0, 0]  # start node distance 0 for both colors
        
        # BFS queue: (node, last_color) where last_color: 0=red, 1=blue
        q = deque()
        q.append((0, 0))  # pretend last was red -> next must be blue
        q.append((0, 1))  # pretend last was blue -> next must be red
        
        visited = set()
        visited.add((0, 0))
        visited.add((0, 1))
        
        while q:
            node, last_color = q.popleft()
            current_dist = dist[node][last_color]
            
            # Next color must be opposite
            next_color = 1 - last_color
            next_adj = blue_adj if next_color == 1 else red_adj
            
            for nei in next_adj[node]:
                if (nei, next_color) not in visited:
                    visited.add((nei, next_color))
                    dist[nei][next_color] = current_dist + 1
                    q.append((nei, next_color))
        
        # Answer: min distance for each node (any ending color)
        ans = []
        for i in range(n):
            min_d = min(dist[i])
            ans.append(min_d if min_d != INF else -1)
        return ans

# ทดสอบ
ob = Solution()
print(ob.shortestAlternatingPaths(3, [[0,1],[1,2]], []))  # [0, 1, -1]
print(ob.shortestAlternatingPaths(3, [[0,1]], [[1,2]]))   # [0, 1, 2] (red then blue)
print(ob.shortestAlternatingPaths(3, [[0,1]], [[0,2]]))   # [0, 1, 1]

Output

[0, 1, -1]
[0, 1, 2]
[0, 1, 1]

การทำงาน BFS (ตัวอย่างแรก)

n=3, red=[[0,1],[1,2]], blue=[]
Start: (0,red) and (0,blue) dist=0

From (0,red) → next must be blue → no blue edges from 0
From (0,blue) → next must be red → red edges from 0: 0→1
  Visit (1,red) dist=1

From (1,red) → next must be blue → no blue edges from 1
Queue empty.

Result: node 0:0, node 1:1, node 2:INF→-1

Complexity

• Time: O(n + R + B) โดย R=red edges, B=blue edges
• Space: O(n + R + B)

สรุป

โจทย์ Shortest Path แบบมี constraint (สลับสี) แก้ได้ด้วย BFS บน State Graph ที่ขยาย state เป็น (node, last_color) ใช้ visited set กันซ้ำ

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ