그래프가 인접 리스트(adjacency list) 형태로 주어졌을 때, 모든 정점 쌍 사이에 경로가 존재하는지를 나타내는 2차원 행렬 M을 구해야 합니다. 행렬의 각 원소는 다음과 같이 정의됩니다.
- M[i, j] = 1 : 정점 i와 정점 j 사이에 경로가 존재하는 경우
- M[i, j] = 0 : 경로가 존재하지 않는 경우
예를 들어 아래와 같은 그래프가 입력으로 주어진다고 가정해 보겠습니다.
이때 기대되는 출력 결과는 다음과 같습니다.
| 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
첫 번째 행이 모두 1인 이유는 정점 0에서 시작하면 그래프의 모든 정점에 도달할 수 있기 때문입니다. 반면 정점 0으로 들어오는 간선이 없으므로, 나머지 정점들의 첫 번째 열은 0이 됩니다.
문제 해결 접근 방법
이 문제는 각 정점에서 출발하여 너비 우선 탐색(BFS)을 수행하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- n x n 크기의 2차원 행렬 ans를 생성하고(n은 정점의 개수), 모든 값을 0으로 초기화합니다.
- i를 0부터 n-1까지 반복합니다.
- 큐 q를 생성하고 i를 삽입합니다.
- q가 빌 때까지 다음을 반복합니다.
- q의 맨 앞 요소를 꺼내 node에 저장합니다.
- ans[i][node]가 이미 1이라면 중복 방문이므로 다음 반복으로 넘어갑니다.
- ans[i][node]를 1로 설정합니다.
- node의 이웃 정점들(graph[node])을 모두 q의 뒤에 추가합니다.
- 모든 반복이 끝나면 ans를 반환합니다.
즉, 각 정점을 시작점으로 삼아 도달할 수 있는 모든 정점을 BFS로 탐색하면서 행렬의 해당 위치를 1로 표시하는 방식입니다. 이미 방문한 노드는 건너뛰므로 불필요한 중복 탐색을 피할 수 있습니다.
구현 예제
class Solution:
def solve(self, graph):
ans = [[0 for _ in graph] for _ in graph]
for i in range(len(graph)):
q = [i]
while q:
node = q.pop(0)
if ans[i][node]:
continue
ans[i][node] = 1
neighbors = graph[node]
for n in neighbors:
q.append(n)
return ans
ob = Solution()
adj_list = [[1, 2], [4], [4], [1, 2], [3]]
print(ob.solve(adj_list))입력
[[1, 2], [4], [4], [1, 2], [3]]
출력
[[1, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 1, 1, 1, 1]]
복잡도 분석
각 정점마다 한 번씩 BFS를 수행하므로 전체 시간 복잡도는 O(V × (V + E))입니다. 여기서 V는 정점의 수, E는 간선의 수입니다. 공간 복잡도는 결과 행렬 때문에 O(V²)가 됩니다. 정점 수가 많아지면 플로이드-워셜(Floyd-Warshall) 알고리즘 등 대안적인 방법과 성능을 비교해 보는 것도 좋습니다.