노드에 0부터 n-1까지 라벨이 붙은 방향 그래프(directed graph)가 있다고 가정해 보겠습니다. 이 그래프의 각 간선은 빨간색 또는 파란색으로 칠해져 있으며, 자기 자신을 향하는 간선(self-edge)이나 두 노드 사이의 평행 간선(parallel edge)도 존재할 수 있습니다. red_edges의 각 [i, j]는 노드 i에서 노드 j로 향하는 빨간색 방향 간선을 의미하고, 마찬가지로 blue_edges의 각 [i, j]는 노드 i에서 노드 j로 향하는 파란색 방향 간선을 의미합니다.
우리가 구해야 할 것은 길이가 n인 배열 answer입니다. 여기서 answer[X]는 노드 0에서 노드 X까지 이동하면서 간선의 색상이 경로를 따라 번갈아 나타나는(예: 빨강 → 파랑 → 빨강 → ...) 최단 경로의 길이를 담고, 그러한 경로가 존재하지 않으면 -1을 저장합니다.
예를 들어 입력이 n = 3, red_edges = [[0,1],[1,2]], blue_edges = []라면 출력은 [0, 1, -1]이 됩니다. 노드 0에서 노드 1까지는 빨간 간선 한 개로 도달 가능하지만, 노드 2는 색상이 번갈아 나오는 조건을 만족하는 경로가 없기 때문입니다.
문제 해결 접근 방법
이 문제는 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 (노드, 직전 간선의 색상) 상태를 함께 관리하는 것입니다. 같은 노드라도 어떤 색의 간선을 통해 도착했는지에 따라 이후에 선택할 수 있는 간선이 달라지기 때문입니다. 단계별로 살펴보겠습니다.
- bfs() 메서드를 정의합니다. 이 메서드는 re(빨간 간선 인접 리스트), be(파란 간선 인접 리스트), f(시작 색상), n을 매개변수로 받습니다.
- visited라는 집합(set)을 정의하고, 큐(queue)를 만들어 삼중항 [0, f, 0]을 삽입합니다. 각 원소는 (노드, 다음 간선 색상, 현재까지 거리)를 의미합니다.
- 큐가 비어 있지 않은 동안 다음을 반복합니다:
- 큐의 맨 앞에서 current(현재 노드), color(색상), step(거리)을 꺼냅니다.
- color 값을 반전시킵니다(true ↔ false). 즉, 다음에 사용할 간선의 색을 결정합니다.
- res[current]를 res[current]와 step 중 더 작은 값으로 갱신합니다.
- color가 참(빨간색)이면 re[current]의 각 노드 i에 대해, (i, color) 쌍이 visited에 없다면 visited에 추가하고 큐에 [i, color, step + 1]을 삽입합니다.
- color가 거짓(파란색)이면 be[current]의 각 노드 i에 대해 동일한 작업을 수행합니다.
- 메인 메서드에서는 다음을 수행합니다:
- 크기가 n이고 모든 값이 무한대(inf)로 초기화된 배열 res를 만듭니다.
- n개의 빈 배열을 담는 인접 리스트 re와 be를 생성합니다.
- r의 각 요소 i에 대해 re[i[0]]에 i[1]을 삽입하여 빨간 간선 정보를 저장합니다.
- b의 각 요소 i에 대해 be[i[0]]에 i[1]을 삽입하여 파란 간선 정보를 저장합니다.
- bfs(re, be, False, n)과 bfs(re, be, True, n)을 각각 호출합니다. 첫 간선이 빨간색인 경우와 파란색인 경우를 모두 고려하기 위함입니다.
- res를 순회하면서 여전히 무한대인 값은 -1로 변경합니다. 이는 해당 노드에 조건을 만족하는 경로가 없다는 뜻입니다.
- res를 반환합니다.
구현 예제 (Python)
아래 구현을 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def shortestAlternatingPaths(self, n, r, b):
self.res = [float("inf")] * n
re = [[] for i in range(n) ]
be = [[] for i in range(n) ]
for i in r:
re[i[0]].append(i[1])
for i in b:
be[i[0]].append(i[1])
self.bfs(re,be,False,n)
self.bfs(re,be,True,n)
for i in range(len(self.res)):
if self.res[i] == float('inf'):
self.res[i]=-1
return self.res
def bfs(self,re,be,f,n):
visited = set()
queue = [[0,f,0]]
while queue:
current,color,step = queue[0]
queue.pop(0)
color = not color
self.res[current] = min(self.res[current],step)
if color:
for i in re[current]:
if (i,color) not in visited:
visited.add((i,color))
queue.append([i,color,step+1])
elif not color:
for i in be[current]:
if (i,color) not in visited:
visited.add((i,color))
queue.append([i,color,step+1])
ob = Solution()
print(ob.shortestAlternatingPaths(3, [[0,1], [1,2]], []))입력
3 [[0,1],[1,2]] []
출력
[0,1,-1]
복잡도 분석
시간 복잡도는 O(n + E)입니다. 여기서 n은 노드 수, E는 전체 간선 수입니다. 각 (노드, 색상) 상태는 최대 한 번만 큐에 들어가고, 각 간선도 최대 두 번 검사되기 때문입니다. 공간 복잡도 역시 visited 집합과 큐에 저장되는 상태의 수에 비례하여 O(n + E)입니다.