인접 리스트 형태로 표현된 무방향 그래프가 주어졌다고 가정해 보겠습니다. 여기서 graph[i]는 노드 i와 인접한 이웃 노드들의 목록을 의미합니다. 우리가 구해야 하는 것은 다음 조건을 만족하는 간선의 개수입니다.
조건: 해당 간선을 제거하면 그래프가 연결 상태를 잃고 분리되는 간선
그래프 이론에서 이런 간선은 브리지(bridge), 즉 '절단 간선'이라고 불립니다.
예를 들어 입력이 다음과 같다면,
graph = [
[0, 2],
[0, 4],
[1, 2, 3],
[0, 3, 4],
[4],
[3],
[2]
]
출력 결과는 1이 됩니다.
문제 해결 접근 방법
이 문제는 DFS(깊이 우선 탐색)를 활용한 대표적인 브리지 찾기 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 각 노드의 깊이(depth)를 기록하고, 해당 노드의 서브트리에서 도달할 수 있는 가장 얕은(작은) 깊이를 추적하는 것입니다. 어떤 자식 노드가 자신보다 위쪽 조상에게 도달하지 못한다면, 부모와 자식을 잇는 간선이 곧 브리지라는 의미입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
dfs(curr, pre, d)함수를 정의합니다. curr은 현재 노드, pre는 직전(부모) 노드, d는 현재 깊이를 나타냅니다.ans를 무한대(INF)로 초기화합니다.dep[curr] := d로 현재 노드의 깊이를 기록합니다.graph[curr]의 모든 인접 노드 adj에 대해 반복합니다.- adj가 직전 노드(pre)와 같다면, 다음 반복으로 건너뜁니다.
dep[adj]가 -1이 아니라면(이미 방문한 노드라면),ans := min(ans, dep[adj])로 갱신합니다.- 그렇지 않다면(아직 방문하지 않았다면), 재귀 호출 결과로
ans := min(ans, dfs(adj, curr, d + 1))을 수행합니다.
- 모든 탐색이 끝난 후,
d > 0이면서d <= ans라면 현재 간선이 브리지이므로re := re + 1로 카운트를 증가시킵니다. ans를 반환합니다.
- 메인 흐름에서는 다음을 수행합니다.
- 그래프 크기만큼의 리스트
dep을 -1로 초기화합니다. - 브리지 개수를 저장할
re := 0으로 초기화합니다. dfs(0, -1, 0)을 호출해 탐색을 시작합니다.re를 반환합니다.
- 그래프 크기만큼의 리스트
아래 구현 예시를 통해 더 쉽게 이해할 수 있습니다.
구현 예시
class Solution:
def solve(self, graph):
dep = [-1] * len(graph)
INF = int(1e9)
self.re = 0
def dfs(curr, pre, d):
ans = INF
dep[curr] = d
for adj in graph[curr]:
if pre == adj:
continue
if dep[adj] != -1:
ans = min(ans, dep[adj])
else:
ans = min(ans, dfs(adj, curr, d + 1))
if d > 0 and d <= ans:
self.re += 1
return ans
dfs(0, -1, 0)
return self.re
ob = Solution()
print(ob.solve(graph = [
[0, 2],
[0, 4],
[1, 2, 3],
[0, 3, 4],
[4],
[3],
[2]
]))
입력
graph = [
[0, 2],
[0, 4],
[1, 2, 3],
[0, 3, 4],
[4],
[3],
[2]
]
출력
1
동작 원리 살펴보기
위 코드에서 dep 배열은 각 노드가 DFS 트리에서 몇 번째 깊이에 위치하는지 저장하고, 변수 ans는 현재 노드의 서브트리에서 역방향 간선을 통해 도달할 수 있는 최소 깊이를 추적합니다. 만약 어떤 노드의 깊이 d가 자신의 서브트리에서 도달 가능한 최소 깊이 ans보다 작거나 같다면(d <= ans), 그 노드는 부모 쪽으로 돌아갈 우회 경로가 없다는 뜻입니다. 따라서 부모와 자신을 연결하는 간선이 곧 브리지가 됩니다.
이 알고리즘은 모든 노드와 간선을 한 번씩만 방문하므로, 시간 복잡도는 O(V + E)(V는 정점 수, E는 간선 수)로 매우 효율적입니다.