Python으로 방향 그래프 반전하기: 인접 리스트 기반 구현 가이드

방향 그래프(directed graph)가 주어졌을 때, 이를 반전(reversal)시킨 그래프를 구하는 문제를 생각해 볼 수 있습니다. 반전이란 간선의 방향을 모두 뒤집는 것으로, 원래 그래프에서 간선이 u에서 v로 향한다면, 반전된 그래프에서는 v에서 u로 향하게 됩니다.

입력은 인접 리스트(adjacency list) 형태로 주어지며, 노드가 총 n개라면 노드 번호는 0부터 n-1까지 차례대로 매겨져 있다고 가정합니다.

예를 들어 다음과 같은 그래프가 입력으로 주어지면,

출력으로는 아래와 같이 모든 간선의 방향이 뒤집힌 그래프를 얻게 됩니다.

문제 해결 접근 방법

이 문제는 각 간선의 방향만 바꿔주면 되므로, 그래프를 한 번 순회하면서 간선 정보를 새로운 인접 리스트에 옮기는 방식으로 간단히 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• 정점 개수만큼 빈 리스트를 원소로 갖는 결과 리스트 ans를 초기화합니다.
• 그래프를 순회하면서 각 인덱스 i와 해당 인접 리스트 l에 대해 다음을 수행합니다.
  • 인접 리스트 l의 각 원소 x에 대해, ans[x]의 끝에 i를 추가합니다. (간선 i → x를 x → i로 뒤집는 과정)
• 모든 순회가 끝나면 ans를 반환합니다.

핵심 아이디어는 간단합니다. 원래 그래프에서 i번 정점이 x번 정점으로 향하는 간선을 갖고 있다면, 반전된 그래프에서는 x번 정점이 i번 정점으로 향하는 간선을 가져야 한다는 점입니다. 따라서 ans[x]에 i를 추가해 주면 됩니다.

구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

class Solution:
   def solve(self, graph):
      ans = [[] for _ in graph]
      for i, l in enumerate(graph):
         for x in l:
            ans[x].append(i)
      return ans
ob = Solution()
graph = [[1,2],[4],[4],[1,2],[3]]
print(ob.solve(graph))

입력

[[1,2],[4],[4],[1,2],[3]]

출력

[[], [0, 3], [0, 3], [4], [1, 2]]

복잡도 분석

이 알고리즘은 그래프의 모든 정점과 간선을 정확히 한 번씩 방문하므로, 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 개수, E는 간선의 개수입니다. 공간 복잡도 역시 반전된 그래프를 저장하기 위해 O(V + E)의 공간이 필요합니다.