유향 그래프(directed graph)의 간선 리스트가 주어졌다고 가정해 봅시다. 그래프에는 n개의 노드가 있으며, 노드 이름은 0부터 n-1까지 번호가 매겨져 있습니다. 또한 두 개의 정수 a와 b가 함께 주어집니다. 우리가 확인해야 할 것은 c에서 출발하여 a에 도달할 수 있고, 동시에 b에도 도달할 수 있는 노드 c가 존재하는지 여부입니다.
예를 들어 위 그래프에서 a = 2, b = 3이라면 결과는 True가 됩니다. c = 0인 경우 0에서 2로 가는 경로와 0에서 3으로 가는 경로가 모두 존재하기 때문입니다.
해결 전략: 깊이 우선 탐색(DFS) 활용
이 문제는 DFS를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 간선 리스트를 역방향 인접 리스트로 변환하는 것입니다. 즉, 간선 (x, y)에 대해 y에서 x로 향하는 형태로 저장하면, 특정 노드에서 DFS를 수행할 때 "그 노드에 도달할 수 있는 모든 노드"를 방문하게 됩니다.
알고리즘 단계
- DFS 함수를 정의합니다. 이 함수는 그래프, 현재 노드, 방문 집합(visited)을 매개변수로 받습니다.
- 현재 노드를 아직 방문하지 않았다면 방문 처리하고, 인접한 모든 노드에 대해 재귀적으로 DFS를 호출합니다.
- 메인 로직에서는 다음을 수행합니다.
- 간선 리스트로부터 인접 리스트를 생성합니다.
- visited_a와 visited_b라는 두 개의 빈 집합을 준비합니다.
- a를 시작점으로 DFS를 수행하고, 이어서 b를 시작점으로 DFS를 수행합니다.
- visited_a와 visited_b의 교집합을 구합니다.
- 교집합이 비어 있지 않으면 True, 비어 있으면 False를 반환합니다.
구현 예제
다음 코드를 통해 실제 구현 과정을 살펴보겠습니다.
def edge_list_to_graph(edges):
s = set()
for x, y in edges:
s.add(x)
s.add(y)
s = len(list(s))
graph = [[] for x in range(s)]
for x, y in edges:
graph[y].append(x)
return graph
def DFS(graph, node, visited):
if node not in visited:
visited.add(node)
for x in graph[node]:
DFS(graph, x, visited)
def solve(edges, a, b):
graph = edge_list_to_graph(edges)
visited_a, visited_b = set(), set()
DFS(graph, a, visited_a)
DFS(graph, b, visited_b)
ans = list(visited_a.intersection(visited_b))
if ans:
return True
return False
ed_list = [(0, 4),(4, 3),(1, 2),(0, 1),(0, 2),(1, 1)]
a = 2
b = 3
print(solve(ed_list, a, b))
코드 설명
- edge_list_to_graph(): 간선 리스트에 등장하는 모든 노드를 수집해 노드 개수를 파악한 뒤, 각 간선 (x, y)에 대해 graph[y]에 x를 추가하는 방식으로 역방향 인접 리스트를 생성합니다.
- DFS(): 재귀적으로 탐색을 수행하며, 아직 방문하지 않은 노드를 집합에 추가하고 연결된 노드들을 계속 따라갑니다.
- solve(): a와 b 각각에 대해 DFS를 실행한 뒤, 두 방문 집합의 교집합을 확인하여 최종 답을 결정합니다.
입력 및 출력
입력
[(0, 4), (4, 3), (1, 2), (0, 1), (0, 2), (1, 1)], 2, 3
출력
True
위 예제에서 노드 0에서 출발하면 0 → 2 경로로 노드 2에 도달할 수 있고, 0 → 4 → 3 경로로 노드 3에도 도달할 수 있습니다. 따라서 두 노드의 공통 출발점 역할을 하는 노드 c = 0이 존재하므로 결과는 True입니다.
이 알고리즘은 DFS를 두 번 수행하므로 시간 복잡도는 O(V + E)(V는 노드 수, E는 간선 수)이며, 공간 복잡도 역시 O(V + E)입니다. 그래프의 크기가 커져도 선형 시간 안에 효율적으로 처리할 수 있다는 장점이 있습니다.