그래프의 개념을 이해하고 이를 실제 코드로 구현할 수 있습니다. 구현 그래프를 탐색하고 최단 경로를 구할 수 있습니다.
총 3편으로 준비했습니다. 3편은 그래프 몸풀기 문제 4개입니다.
1. 그래프의 개념
2. 그래프 탐색
3. 그래프 몸풀기 문제
문제 01 깊이 우선 탐색 순회 ⭐️
- 저자 권장 시간: 30분
- 권장 시간 복잡조: O(N+E)
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/38.py
깊이 우선 탐색으로 모든 그래프의 노드를 순회하는 함수 solution( )을 작성하세요. 시작 노드는 start로 주어집니다. graph는 [출발 노드, 도착 노드] 쌍들이 들어 있는 리스트입니다. 반환값은 그래프의 시작 노드부터 모든 노드를 깊이 우선 탐색으로 진행한 순서대로 노드가 저장된 리스트입니다.
제약 조건
- 노드의 최대 개수는 100개를 넘지 않습니다.
- 시작 노드부터 시작해서 모든 노드를 방문할 수 있는 경로가 항상 있습니다.
- 그래프의 노드는 문자열입니다.
입출력의 예
문제 분석하고 풀기
앞서 공부한 깊이 우선 탐색을 구현하고, 순회한 결과를 출력하는 문제입니다. 입출력 예를 보면 [출발 노드, 도착 노드]의 쌍이 리스트로 들어옵니다. 첫 번째 graph를 그림으로 표현하면 다음과 같습니다.
graph로 주어진 값을 인접 리스트로 변환하여 그래프를 저장하기만 하면 깊이 우선 탐색을 쉽게 구현할 수 있습니다. 코드는 다음과 같습니다.
from collections import defaultdict
def solution(graph, start):
# ❶ 그래프를 인접 리스트로 변환
adj_list = defaultdict(list)
for u, v in graph:
adj_list[u].append(v)
# ❷ DFS 탐색 함수
def dfs(node, visited, result):
visited.add(node) # ❸ 현재 노드를 방문한 노드들의 집합에 추가
result.append(node) # ❹ 현재 노드를 결과 리스트에 추가
for neighbor in adj_list.get(node, []): # ❺ 현재 노드와 인접한 노드순회
if neighbor not in visited: # ❻ 아직 방문하지 않은 노드라면
dfs(neighbor, visited, result)
# DFS를 순회한 결과를 반환
visited = set()
result = []
dfs(start, visited, result) # ❼ 시작 노드에서 깊이 우선 탐색 시작
return result # ❽ DFS 탐색 결과 반환
defaultdict 클래스로 그래프를 인접 리스트로 변환했습니다. defaultdict 클래스는 키가 없을 때 기본값을 defaultdict 형태로 기본값을 지정합니다. 예를 들어 defaultdict(list)라고 작성하면 기본값은 [ ]와 같이 초기화합니다.
from collections import defaultdict
# defaultdict를 생성하고 초깃값으로 str('')을 지정합니다.
my_dict_str = defaultdict(str)
# defaultdict를 생성하고 초깃값으로 list([])을 지정합니다.
my_dict_list = defaultdict(list)
# 각 defaultdict에서 키에 접근하여 값을 확인합니다.
print(my_dict_str['key']) # 출력 : ''
print(my_dict_list['key']) # 출력 : []
# 값 추가 및 조작을 수행합니다.
my_dict_str['key'] += 'Hello'
my_dict_list['key'].append(4)
# 각 defaultdict에서 키에 접근하여 값을 확인합니다.
print(my_dict_str['key']) # 출력 : 'Hello'
print(my_dict_list['key']) # 출력 : [4]
❶ adj_list 변수는 defaultdict(list)로 초기화한 다음 adj_list[u]에 v를 대입하는 방식으로 인접 리스트를 만들었습니다. ❷ 그런 다음 깊이 우선 탐색을 수행할 dfs( ) 함수를 정의합니다. ❸ 이 함수는 노드(node)를 방문한 다음, 방문한 노드(visited)들의 집합에 방문한 노드를 추가합니다. ❹ result에도 방문한 노드를 추가하고, ❺ 인접한 노드를 하나씩 방문하면서 ❻ 아직 방문하지 않은 노드라면, 해당 노드를 다음 노드로 하여 dfs( ) 함수를 재귀 호출합니다. 이제 dfs( ) 함수에 대한 설명을 마쳤습니다. solution( ) 함수는 ❼ 시작 노드 start부터 깊이 우선 탐색 알고리즘을 수행합니다. ❽ 깊이 우선 탐색을 끝내면 result 리스트를 반환합니다.
시간 복잡도 분석하기
노드의 개수를 N, 간선의 개수를 E라고 하면 인접 리스트를 생성할 때는 간선 개수만큼 연산하므로 시간 복잡도는 O(E)가 되고, 탐색 시 모든 노드를 1회 방문하므로 N번 방문합니다. 따라서 깊이 우선 탐색의 시간 복잡도는 O(N + E)입니다.
문제 02 너비 우선 탐색 순회 ⭐️
- 저자 권장 시간: 30분
- 권장 시간 복잡조: O(N+E)
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/39.py
너비 우선 탐색으로 모든 노드를 순회하는 함수 solution( )을 작성하세요. 시작 노드는 매개변수 start로 주어집니다. graph는 (출발 노드, 도착 노드) 쌍들이 들어 있는 리스트입니다. 반환값은 그래프의 시작 노드부터 모든 노드를 너비 우선 탐색으로 진행한 순서대로 노드가 저장된 리스트입니다.
제약 조건
- 노드의 최대 개수는 100개입니다.
- 시작 노드부터 시작해서 모든 노드를 방문할 수 있는 경로가 항상 있습니다.
- 그래프의 노드는 숫자입니다.
입출력의 예
문제 분석하고 풀기
깊이 우선 탐색과 같은 종류의 문제입니다. 지금까지 공부한 내용이면 충분히 이 문제를 풀 수 있을 겁니다. 바로 코드를 구현해보겠습니다.
from collections import defaultdict, deque
def solution(graph, start):
# 그래프를 인접 리스트로 변환
adj_list = defaultdict(list)
for u, v in graph:
adj_list[u].append(v)
# BFS 탐색 함수
def bfs(start):
visited = set() # ❶ 방문한 노드를 저장할 셋
# ❷ 탐색시 맨 처음 방문할 노드 푸시 하고 방문처리
queue = deque([start])
visited.add(start)
result.append(start)
# ❸ 큐가 비어있지 않은 동안 반복
while queue:
node = queue.popleft() # ❹ 큐에 있는 원소 중 가장 먼저 푸시된 원소 팝
for neighbor in adj_list.get(node, []): #❺ 인접한 이웃 노드들에 대해서
if neighbor not in visited: # ❻ 방문되지 않은 이웃 노드인 경우
# ❼ 이웃노드를 방문 처리함
queue.append(neighbor)
visited.add(neighbor)
result.append(neighbor)
result = []
bfs(start) # ❽ 시작 노드부터 BFS 탐색 수행
return result
adj_list는 주어진 그래프를 인접 리스트로 표현하기 위한 변수입니다. 인수로 받은 그래프의 각 간선 정보를 활용해서 인접 리스트를 만듭니다. 너비 우선 탐색 구현 부분은 다음과 같습니다.
❶ visited의 목적은 한 번 방문한 노드를 체크해서 다시 방문하지 않도록 하는 것입니다. ❷ 시작 노드부터 너비 우선 탐색을 할 수 있도록 큐에 시작 노드를 넣고 방문 처리합니다. deque( ) 함수의 인수로 start가 아닌 [start]를 넣은 부분은 코딩을 할 때 실수하기 쉬운 부분이므로 꼭 기억하세요. dequeue( ) 함수는 이터러블 객체를 인수로 받습니다. ❸ 시작 노드를 기준으로 너비 우선 탐색을 진행합니다. 큐가 비는 시점, 즉, 방문할 수 있는 모든 노드에 방문할 때까지 탐색을 진행합니다. ❹ 현재 팝한 노드의 인접 노드들을 방문할 것입니다. ❺ node와 인접한 노드들을 순회하면서 ❻ 인접한 노드 중 방문하지 않은 노드가 있다면 ❼ 해당 노드를 방문 처리하고 푸시합니다. 인접한 노드를 방문 처리할 때 최종 반환한 result에서 노드를 푸시하고 있는 것을 볼 수 있습니다. 여기까지가 너비 우선 탐색 동작입니다. ➑ 시작 노드부터 너비 우선 탐색을 하도록 bfs(start)와 같이 호출합니다.
시간 복잡도 분석하기
노드의 개수를 N, 간선의 개수를 E라고 하면 인접 리스트를 생성할 때는 간선 개수만큼 연산하므로 시간 복잡도는 O(E)가 되고, 탐색 시 모든 노드를 1회 방문하므로 N번 방문합니다. 따라서 너비 우선 탐색의 시간 복잡도는 O(N + E)입니다.
문제 03 다익스트라 알고리즘 ⭐️⭐️⭐️
- 저자 권장 시간: 60분
- 권장 시간 복잡조: O((N+E)logN)
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/40.py
주어진 그래프와 시작 노드를 이용하여 다익스트라 알고리즘을 구현하는 solution( ) 함수를 작성하세요. 인수는 graph, start 총 2개입니다. graph는 딕셔너리로 주어지며 노드의 연결 정보와 가중치가 저장되어 있습니다. 예를 들어 {‘A’: {‘B’: 2, ‘C’: 5}}이면 A는 B, C에 각각 가중치 2, 5로 연결되어 있는 것입니다. start는 문자열로 주어지며 출발 노드를 의미합니다. 반환값은 시작 노드부터, 각 노드까지 최소 비용과 최단 경로를 포함한 리스트입니다.
제약 조건
- 그래프의 노드 개수는 최대 10,000개입니다.
- 각 노드는 0 이상의 정수로 표현합니다.
- 모든 가중치는 0 이상의 정수이며 10,000을 넘지 않습니다.
입출력의 예
예를 들어 첫 번째 입력에 대한 결과를 그림으로 나타내면 다음과 같습니다. 반환값을 분석하면 시작 노드를 기준으로 B의 최소 비용은 4이고, 최단 경로는 A → C → B입니다.
문제 분석하고 풀기
이 문제에서는 우선 순위 큐(heap) 자료구조로 최단 거리를 관리합니다. 문제에서 주어진 그래프가 딕셔너리인 점도 눈여겨보기 바랍니다.
import heapq
def solution(graph, start):
distances = {node: float("inf") for node in graph} # ❶ 모든 노드의 거리 값을 무한대로 초기화
distances[start] = 0 # ❷ 시작 노드의 거리 값은 0으로 초기화
queue = []
heapq.heappush(queue, [distances[start], start]) # ❸ 시작 노드를 큐에 삽입
paths = {start: [start]} # ❹ 시작 노드의 경로를 초기화
while queue:
# ❺ 현재 가장 거리 값이 작은 노드를 가져옴
current_distance, current_node = heapq.heappop(queue)
# ❻ 만약 현재 노드의 거리 값이 큐에서 가져온 거리 값보다 크면, 해당 노드는 이미 처리한 것이므로 무시
if distances[current_node] < current_distance:
continue
# ❼ 현재 노드와 인접한 노드들의 거리 값을 계산하여 업데이트
for adjacent_node, weight in graph[current_node].items():
distance = current_distance + weight
# ❽ 현재 계산한 거리 값이 기존 거리 값보다 작으면 최소 비용 및 최단 경로 업데이트
if distance < distances[adjacent_node]:
distances[adjacent_node] = distance # 최소 비용 업데이트
paths[adjacent_node] = paths[current_node] + [adjacent_node] # 최단 경로 업데이트
# ➒ 최소 경로가 갱신된 노드를 비용과 함께 큐에 푸시
heapq.heappush(queue, [distance, adjacent_node])
# ➓ paths 딕셔너리를 노드 번호에 따라 오름차순 정렬하여 반환
sorted_paths = {node: paths[node] for node in sorted(paths)}
return [distances, sorted_paths]
❶ distances는 시작 노드부터 모든 노드의 최소 비용을 담을 딕셔너리입니다. 초기에는 모든 노드의 최소 비용을 무한대로, ❷ 시작 노드의 최소 비용은 0으로 정합니다. ❸ heapq는 우선순위큐입니다. 우선순위 큐는 푸시 순서와 상관없이 heapq에서 정한 우선순위에 따라 팝합니다. 현재는 오름차순으로 팝합니다. 이렇게 오름차순으로 팝하는 heapq의 특성을 이용하면 선택되지 않은 노드 중 최소 비용이 가장 적은 노드를 팝할 수 있습니다. ❹ paths는 최소 비용의 세부 경로, 즉, 최단 경로를 저장할 딕셔너리입니다. 각 노드의 최단 경로의 시작 노드는 start이므로 시작 노드로 초기화합니다. ❺ 현재 선택하지 않은 노드 중 가장 가중치가 적은 노드와 최소 비용을 가져옵니다. ❻ current_node에 대해서 우선순위 큐에서 팝한 노드의 비용 current_distance가 현재까지 구한 최소 비용 distance[current_node]보다 크면 이미 방문한 것이므로 푸시합니다. ❼ 거쳐가는 노드 current_node와 인접한 노드 adjacent_node의 최소 비용 및 최단 경로를 갱신하기 위해 순회합니다. ❽ 현재까지 구한 최소 비용보다 current_node를 거치는 비용이 더 적으면 최소 비용과 최단 경로를 갱신합니다. ❾ 최소 비용이 갱신된 노드와 최소 비용을 우선순위 큐에 푸시합니다. ❿ 최단 경로는 노드를 오름차순으로 정렬해서 반환합니다.
※ 우선순위 큐는 ‘정렬 알아보기’에서 자세히 공부합니다.
시간 복잡도 분석하기
노드의 개수를 N, 간선의 개수를 E라고 하겠습니다. distances 배열을 초기화할 때의 시간 복잡도는 O(N)입니다. 반복문을 보면 현재 노드의 거리가 우선순위 큐에서 가져온 거리보다 작으면 무시하고 이 연산은 최대 N번 수행하므로 시간 복잡도는 O(N * logN)입니다. 이후 최단 거리를 갱신하는 동작은 최대 E번 수행하므로 시간 복잡도는 O(E * logN)입니다. 여기까지가 다익스트라 알고리즘 동작이고, 시간 복잡도를 종합하여 계산하면 O((N + E)logN)입니다. 마지막으로 딕셔너리를 정렬하므로 이것에 대한 시간 복잡도는 O(NlogN)인데, 이것을 고려해도 시간 복잡도는 변함없이 O((N + E)logN)입니다.
문제 04 벨만-포드 알고리즘 ⭐️⭐️⭐️
- 저자 권장 시간: 60분
- 권장 시간 복잡조: O(N*E))
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/41.py
벨만-포드 알고리즘을 구현한 solution( ) 함수를 구현하세요. graph의 각 데이터는 리스트입니다. 첫 번째 데이터는 0번 노드 기준으로 연결된 노드 정보, 두 번째 데이터는 1번 노드 기준으로 연결된 노드 정보입니다. 노드 정보의 구성은 (노드, 가중치)와 같습니다. source는 시작 노드입니다. 반환값은 최단 거리를 담은 distance 리스트와 최단 거리와 함께 관리할 직전 노드 predecessor를 리스트에 차례대로 담아서 [distance, predecessor] 형식으로 반환하면 됩니다. predecessor에서 시작 노드는 None으로 표시합니다. 만약 음의 가중치 순회가 있다면 [-1]을 반환하세요. 음의 가중치 순회란 순환하면 할수록 가중치의 합이 적어지는 순회를 말합니다.
제약 조건
- 노드의 최대 개수는 100개입니다.
- 각 간선의 가중치는 -100 이상 100 이하입니다.
입출력의 예
예를 들어 입력에 있는 그래프는 다음과 같습니다.
두 번째 그래프의 경우 음의 가중치 순회가 존재하므로, [-1]이 반환된 것을 알 수 있습니다.
문제 분석하고 풀기
벨만-포드 알고리즘의 목적을 다시 생각해봅시다. 이 알고리즘의 목적은 시작 노드로부터 모든 노드까지의 최단 경로를 찾는 것이었습니다. 이를 위해 각 노드까지의 최단 거리를 추정하고, 이 거리를 개선해나갔죠. 벨만-포드 알고리즘은 모든 간선에 대하여 가중치를 계산, 비교 연산을 매번합니다. 이 점을 기억하며 코드를 작성해봅시다.
def solution(graph, source):
# ➊ 그래프의 노드 수
num_vertices = len(graph)
# ➋ 거리 배열 초기화
distance = [float("inf")] * num_vertices
distance[source] = 0
# ➌ 직전 경로 배열 초기화
predecessor = [None] * num_vertices
# ➍ 간선 수 만큼 반복하여 최단 경로 갱신
for temp in range(num_vertices - 1):
for u in range(num_vertices):
for v, weight in graph[u]:
# ➎ 현재 노드 u를 거쳐서 노드 v로 가는 경로의 거리가 기존에 저장된 노드 v까지의 거리보다 짧은 경우
if distance[u] + weight < distance[v]:
# ➏ 최단 거리를 갱신해줍니다.
distance[v] = distance[u] + weight
# ➐ 직전 경로를 업데이트합니다.
predecessor[v] = u
# ➑ 음의 가중치 순회 체크
for u in range(num_vertices):
for v, weight in graph[u]:
# ➒ 현재 노드 u를 거쳐서 노드 v로 가는 경로의 거리가 기존에 저장된 노드 v까지의 거리보다 짧은 경우
if distance[u] + weight < distance[v]:
# ❿ 음의 가중치 순회가 발견되었으므로 [-1]을 반환합니다.
return [-1]
return [distance, predecessor]
➊ len(graph)로 그래프의 노드 개수를 센 다음 num_vertices 변수에 저장합니다. ➋ distance 배열에 최소 비용을 저장합니다. 처음에는 모든 값을 양의 무한대 float(‘inf’)으로 초기화합니다. distance[source] = 0으로 출발 노드의 최소 비용을 초기화합니다. ➌ predecessor 배열은 직전 경로를 저장하는 배열입니다. 모든 값을 None으로 초기화합니다. ➍ num_vertices – 1만큼 반복하며 최단 경로를 갱신합니다. ➎ graph[u]는 노드 u에서 출발하는 간선들의 리스트입니다. for v, weight in graph[u]로 노드 u와 연결된 각 노드 v와 가중치 weight를 순회합니다. ➏ 현재 노드 u를 거쳐서 노드 v로 가는 경로의 거리가 기존 노드 v까지의 거리보다 짧으면 최소 비용과 ➐ 직전 노드를 갱신합니다.
➑ 음의 가중치 순회를 체크하기 위해 모든 한 번 더 모든 간선들의 최소 비용 업데이트를 시도합니다. ➒ 만약 최소 비용이 갱신되는 노드가 있다면 ➓ 음의 가중치 순회가 존재하는 것이므로 [-1]을 반환합니다.
시간 복잡도 분석하기
노드의 개수를 N, 간선의 개수를 E라고 하겠습니다. 노드 개수에서 1을 뺀만큼 최단 경로를 체크하며 필요한 경우 갱신 연산을 하므로 시간 복잡도는 O(N * E)입니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
