💻 [코테06] 11장 그래프

11장. 그래프

11-1. 그래프의 개념

• 노드와 간선을 이용한 비선형 데이터 구조
• 보통 데이터 간의 관계를 표현하는데 사용
• 데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현
• 간선은 방향이 있는 경우, 없는 경우 모두 가능
• 관계나 흐름에서 정도를 표현할 필요가 있다면 가중치 추가하여 표현

1) 그래프의 특징과 종류

• 흐름을 표현하는 방향성(방향 그래프, 무방향 그래프)
• 흐름의 정도를 표현하는 가중치(가중치 그래프)
• 시작과 끝의 연결 여부를 보는 순환(순환 그래프, 비순환 그래프)

2) 그래프 구현

• 인접 행렬을 통한 그래프 구현
  • 인접 행렬은 배열을 활용하여 구현
  • 노드 : 배열의 인덱스
  • 가중치 : 배열의 값
  • 출발 노드 : 인덱스의 세로 방향
  • 도착 노드 : 인덱스의 가로 방향
• 인접 리스트를 통한 그래프 구현

11-2. 그래프 탐색

1) 깊이우선 탐색 순회

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 탐색 결과 반환

# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution([['A', 'B'], ['B', 'C'], ['C', 'D'], ['D', 'E']], 'A')) # 반환값 : ['A', 'B', 'C', 'D', 'E']
# print(solution([['A', 'B'], ['A', 'C'], ['B', 'D'], ['B', 'E'], ['C', 'F'], ['E', 'F']], 'A')) # 반환값 : ['A', 'B', 'D', 'E', 'F', 'C']

2) 너비우선 탐색 순회

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

# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution([(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 8), (6, 9), (7, 9)],1)) # 반환값 :[1, 2, 3, 4, 5, 6, 7, 8, 9]
# print(solution([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)],1)) # 반환값 : [1, 2, 3, 4, 5, 0]
 

3) 다익스트라 알고리즘

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]


# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution({ 'A': {'B': 9, 'C': 3}, 'B': {'A': 5}, 'C': {'B': 1} },'A')) # 반환값 :[{'A': 0, 'B': 4, 'C': 3}, {'A': ['A'], 'B': ['A', 'C', 'B'], 'C': ['A', 'C']}]
# print(solution({'A': {'B': 1},'B': {'C': 5},'C': {'D': 1},'D': { } }, 'A')) # 반환값 :[{'A': 0, 'B': 1, 'C': 6, 'D': 7}, {'A': ['A'], 'B': ['A', 'B'], 'C': ['A', 'B', 'C'], 'D': ['A', 'B', 'C', 'D']}]

4) 벨만-포드 알고리즘

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]

# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution([[(1, 4), (2, 3), (4, -6 )], [(3, 5)], [(1, 2)], [(0, 7), (2, 4)],[(2, 2)]],0)) #반환갑 : [[0, -2, -4, 3, -6], [None, 2, 4, 1, 0]]
# print(solution([[(1, 5), (2, -1)], [(2, 2)], [(3, -2)], [(0, 2), (1, 6)]],0)) # 반환값 : [-1]

11-3. 합격자가 되는 모의 테스트

문제42_게임 맵 최단 거리
문제43_네트워크
문제44_배달