문제 개요
방향 그래프(directed graph)의 인접 리스트(adjacency list)가 주어진다고 가정해 봅시다. 각 인덱스 i에 있는 리스트는 노드 i에서 연결되는 노드들을 나타냅니다. 여기에 목표 값(target)도 함께 주어지며, 우리가 구해야 할 것은 이 target 노드를 포함하는 가장 짧은 사이클의 길이입니다. 만약 해당하는 사이클이 존재하지 않는다면 -1을 반환하면 됩니다.
예를 들어 아래와 같은 그래프가 입력으로 주어졌다고 하겠습니다.
이때 target = 3이라면 출력 결과는 3이 됩니다. 그 이유는 노드 1 → 2 → 3 → 1로 이루어진 사이클이 존재하기 때문입니다. 참고로 0 → 1 → 2 → 3 → 0이라는 또 다른 사이클도 있지만, 이것은 최단 사이클이 아니므로 정답에서 제외됩니다.
해결 접근 방식: 너비 우선 탐색(BFS)
이 문제는 본질적으로 target 노드에서 출발하여 다시 target으로 돌아오는 최단 경로를 찾는 것과 같습니다. 따라서 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. BFS는 레벨 단위로 탐색하기 때문에, 처음으로 target에 도달했을 때의 레벨이 곧 최단 사이클의 길이가 됩니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- visited: 이미 방문한 노드를 저장하는 새로운 집합(set)을 생성합니다.
- l: 시작점인 target을 담고 있는 리스트를 생성합니다.
- length: 사이클 길이를 나타내는 변수로 0으로 초기화합니다.
- l이 비어 있지 않은 동안 다음을 반복합니다:
- length를 1 증가시킵니다.
- 다음 레벨의 노드들을 저장할 새로운 리스트 nl을 생성합니다.
- l에 있는 각 노드 u에 대해:
- graph[u]에 있는 각 노드 v에 대해:
- v가 target과 같다면 현재 length를 반환합니다. (최단 사이클 발견)
- v가 이미 방문한 노드라면 다음 반복으로 건너뜁니다.
- v를 방문 처리하고 nl의 끝에 추가합니다.
- l을 nl로 갱신하여 다음 레벨 탐색을 준비합니다.
구현 예제
아래 파이썬 코드를 통해 위 알고리즘을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, graph, target):
visited = set()
l = [target]
length = 0
while l:
length += 1
nl = []
for u in l:
for v in graph[u]:
if v == target:
return length
if v in visited:
continue
visited.add(v)
nl.append(v)
l = nl
return -1
ob = Solution()
graph = [[1, 4],[2],[3],[0, 1],[]]
target = 3
print(ob.solve(graph, target))입력
[[1, 4],[2],[3],[0, 1],[]]
출력
3
동작 원리 상세 분석
주어진 그래프에서 각 노드의 연결 관계는 다음과 같습니다.
- 노드 0 → 노드 1, 노드 4
- 노드 1 → 노드 2
- 노드 2 → 노드 3
- 노드 3 → 노드 0, 노드 1
- 노드 4 → 연결된 노드 없음
BFS 첫 번째 레벨에서 target(노드 3)의 인접 노드인 0과 1을 탐색합니다. 두 번째 레벨에서는 노드 0의 인접 노드인 1(이미 방문됨), 4와 노드 1의 인접 노드인 2를 탐색합니다. 세 번째 레벨에서 노드 4의 인접 노드는 없고, 노드 2의 인접 노드인 3이 바로 target이므로 length 3이 반환됩니다. 이는 실제 사이클 3 → 1 → 2 → 3의 길이와 일치합니다.
시간 및 공간 복잡도
- 시간 복잡도: O(V + E) — 모든 정점(V)과 간선(E)을 최대 한 번씩만 방문합니다.
- 공간 복잡도: O(V) — visited 집합과 큐 역할을 하는 리스트에 최대 V개의 노드가 저장될 수 있습니다.
이처럼 BFS를 활용하면 방향 그래프에서 특정 노드를 포함하는 최단 사이클을 선형 시간 내에 효율적으로 찾을 수 있습니다.