문제 개요
0부터 n-1까지의 숫자로 표현되는 n개의 도시가 있고, 한 도시를 다른 도시와 연결하는 일방통행 도로 목록이 주어집니다. 이때 어떤 도시에서 출발하더라도 나머지 모든 도시에 도달할 수 있는지 확인해야 합니다.
예를 들어, 입력이 n = 3, roads = [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]이라면 출력은 True가 됩니다. 0번 도시에서 1번으로 갈 수 있고, 1번에서도 0번으로 돌아올 수 있기 때문입니다. 실제로 모든 도시 쌍 사이에 왕복 경로가 존재합니다.
해결 접근 방법
핵심 아이디어는 다음과 같습니다. 어떤 그래프에서 모든 도시가 서로에게 도달 가능하려면, 원래 그래프와 방향을 뒤집은 역방향 그래프 양쪽 모두에서 하나의 시작점(예: 0번 도시)으로부터 모든 노드에 도달할 수 있어야 합니다.
구체적인 단계는 아래와 같습니다.
- dfs() 함수 정의: 매개변수는 i(현재 노드), visited(방문 집합), g(그래프)입니다.
i를 방문 처리한 뒤, g[i]에 연결된 각 노드 j에 대해 방문하지 않았다면 재귀적으로 dfs(j, visited, g)를 호출합니다. - travel() 함수 정의: 매개변수는 g(그래프)입니다.
빈 집합 visited를 만들고 dfs(0, visited, g)를 실행한 후, visited의 크기가 n과 같으면 True를 반환합니다. 즉, 0번 도시에서 모든 도시에 도달했는지 검사합니다. - 메인 로직:
그래프(graph)와 역방향 그래프(rev_graph)를 생성합니다. 도로 정보(u → v)를 순회하면서 graph[u]에 v를 추가하고, rev_graph[v]에 u를 추가합니다.
마지막으로 travel(graph)와 travel(rev_graph)가 모두 참일 때 True를 반환합니다.
구현 예제
class Solution:
def solve(self, n, roads):
from collections import defaultdict
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in roads:
graph[u].append(v)
rev_graph[v].append(u)
def dfs(i, visited, g):
visited.add(i)
for j in g[i]:
if j not in visited:
dfs(j, visited, g)
def travel(g):
visited = set()
dfs(0, visited, g)
return len(visited) == n
return travel(graph) and travel(rev_graph)
ob = Solution()
n = 3
roads = [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
print(ob.solve(n, roads))입력
3, [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
출력
True
동작 원리 설명
위 코드에서 travel() 함수는 DFS(깊이 우선 탐색)를 이용해 0번 도시에서 출발하여 도달할 수 있는 모든 도시를 visited 집합에 기록합니다. 만약 visited의 크기가 전체 도시 수 n과 같다면, 0번 도시에서 모든 도시로 이동이 가능하다는 의미입니다.
그러나 일방통행 도로만 있으므로 '갈 수 있다'고 해서 '돌아올 수 있다'는 보장이 없습니다. 따라서 모든 도로의 방향을 반대로 뒤집은 rev_graph에 대해서도 동일한 검사를 수행합니다. 두 검사가 모두 통과하면, 임의의 도시 A에서 도시 B로 가는 경로와 그 역경로가 모두 존재함을 알 수 있습니다. 이는 곧 그래프가 강하게 연결(strongly connected)되어 있다는 뜻이며, 어떤 도시에서 출발하더라도 모든 도시에 도달할 수 있음을 보장합니다.
시간 복잡도
DFS는 각 노드와 간선을 최대 한 번씩만 방문하므로, 시간 복잡도는 O(V + E)입니다. 여기서 V는 도시 수(n), E는 도로 수입니다. 그래프와 역방향 그래프에 대해 각각 한 번씩 수행하므로 전체 복잡도 역시 O(V + E)로 효율적입니다.