그래프 - 몸풀기 문제

### 문제 38 깊이 우선 탐색 순회

시작 노드는 start로
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

defaultdict는 특정 기본값을 가지는 딕셔너리를 쉽게 생성하고 관리함
defaultdict(list) 라고 작성하면 기본값은 [] 로 초기화

시간복잡도는 O(V+E)
인접리스트를 생성할 때 간선 개수만큼 연산하고, 탐색시 모든 노드를 1회 방문하므로

추가 설명

graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
}
start = 1

1. 재귀 방식

코드

def dfs_recursive(node, visited, result):
    visited.add(node)  # 현재 노드 방문
    result.append(node)  # 결과 리스트에 추가

    # 인접 노드 탐색
    for neighbor in graph[node]:
        if neighbor not in visited:  # 방문하지 않은 노드만 탐색
            dfs_recursive(neighbor, visited, result)
            
visited = set()
result = []
dfs_recursive(1, visited, result)
print(result)

재귀 방식에서 이전 호출로 복귀는 암묵적으로 이루어짐
Python의 재귀 함수 호출은 내부적으로 호출 스택을 사용하며, 함수 호출이 끝나면 자동으로 이전 호출로 복귀함

처리 과정

1단계: 초기 호출

• 함수 호출: dfs_recursive(1, visited, result)
• 1을 방문:
  • visited = {1}
  • result = [1]
• 인접 노드 탐색:
  • 첫 번째 인접 노드 2 탐색.

2단계: 2 방문

• 함수 호출: dfs_recursive(2, visited, result)
• 2를 방문:
  • visited = {1, 2}
  • result = [1, 2]
• 인접 노드 탐색:
  • 첫 번째 인접 노드 4 탐색.

3단계: 4 방문

• 함수 호출: dfs_recursive(4, visited, result)
• 4를 방문:
  • visited = {1, 2, 4}
  • result = [1, 2, 4]
• 인접 노드 없음:
  • 함수 종료, 이전 호출(2)로 복귀.

4단계: 2로 복귀

• 남은 인접 노드 없음.
• 함수 종료, 이전 호출(1)로 복귀.

5단계: 1로 복귀, 3 탐색

• 함수 호출: dfs_recursive(3, visited, result)
• 3을 방문:
  • visited = {1, 2, 3, 4}
  • result = [1, 2, 4, 3]
• 인접 노드 탐색:
  • 첫 번째 인접 노드 5 탐색.

6단계: 5 방문

• 함수 호출: dfs_recursive(5, visited, result)
• 5를 방문:
  • visited = {1, 2, 3, 4, 5}
  • result = [1, 2, 4, 3, 5]
• 인접 노드 없음:
  • 함수 종료, 이전 호출(3)로 복귀.

7단계: 탐색 종료

• 모든 인접 노드를 방문했으므로 탐색 종료.

결과

[1, 2, 4, 3, 5]

2. 스택 방식

코드

def dfs_stack(start, graph):
    visited = set()
    stack = [start]
    result = []

    while stack:
        node = stack.pop()  # 스택에서 노드 꺼냄
        if node not in visited:  # 방문하지 않은 노드라면
            visited.add(node)  # 방문 처리
            result.append(node)  # 결과 리스트에 추가
            
            # 스택에 인접 노드 추가 (역순으로 넣어야 재귀 방식과 순서 일치)
            for neighbor in reversed(graph[node]):
                stack.append(neighbor)
    return result

result = dfs_stack(1, graph)
print(result)

처리 과정

1단계: 초기 상태

• 스택: [1]
• 방문: {}
• 결과: []

2단계: 1 방문

• 스택에서 1 꺼냄.
• 방문 처리: visited = {1}
• 결과에 추가: result = [1]
• 인접 노드 [2, 3]을 역순으로 스택에 추가:
  • 스택: [3, 2]

3단계: 2 방문

• 스택에서 2 꺼냄.
• 방문 처리: visited = {1, 2}
• 결과에 추가: result = [1, 2]
• 인접 노드 [4]를 스택에 추가:
  • 스택: [3, 4]

4단계: 4 방문

• 스택에서 4 꺼냄.
• 방문 처리: visited = {1, 2, 4}
• 결과에 추가: result = [1, 2, 4]
• 인접 노드 없음.
• 스택: [3]

5단계: 3 방문

• 스택에서 3 꺼냄.
• 방문 처리: visited = {1, 2, 3, 4}
• 결과에 추가: result = [1, 2, 4, 3]
• 인접 노드 [5]를 스택에 추가:
  • 스택: [5]

6단계: 5 방문

• 스택에서 5 꺼냄.
• 방문 처리: visited = {1, 2, 3, 4, 5}
• 결과에 추가: result = [1, 2, 4, 3, 5]
• 인접 노드 없음.
• 스택: []

7단계: 탐색 종료

• 스택이 비었으므로 탐색 종료.

결과

[1, 2, 4, 3, 5]

---

### 문제 38 너비 우선 탐색 순회

시작노드는 매개변수 start로 주어짐
graph는 (출발노드, 도착노드) 쌍들이 들어 있는 리스트
반환값은 그래프의 시작 노드부터 모든 노드를 너비 우선 탐색으로 진행한 순서대로 노드가 저장된 리스트

from collections import defaultdict

# 그래프를 인접리스트로 변환
def solution(graph,start):
	adj_list=defaultdic([])
    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)
    
    whlie queue:
    	node=popleft()
        for neighbor in adj_list.get([node,[]):
        	queue.append(neighbor)
            visited.append(neighbor) # 인접한 노드를 바로 방문 처리
            result.append(neighbor)
            
result=[]
bfs(start)
return result

시간복잡도는 O(V+E)
인접리스트를 생성할 때 간선 개수만큼 연산하고, 탐색시 모든 노드를 1회 방문하므로

추가 설명

그래프 입력:

graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
}
start = 1

from collections import deque

def bfs(start, graph):
    visited = set()  # 방문한 노드들을 저장
    queue = deque([start])  # 탐색을 위한 큐 초기화
    result = []  # 탐색 결과를 저장할 리스트

    while queue:  # 큐가 비어있지 않을 때까지 반복
        node = queue.popleft()  # 큐에서 노드를 꺼냄
        if node not in visited:  # 방문하지 않은 노드라면
            visited.add(node)  # 방문 처리
            result.append(node)  # 결과 리스트에 추가

            # 인접 노드들을 큐에 추가 (추가해도 어차피 pop 되는 건 그 전에 넣어놓은 거)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
    return result

실행:

result = bfs(start, graph)
print(result)

출력:

[1, 2, 3, 4, 5]

큐와 결과 리스트의 상태 변화:

1. 초기 상태:
   • queue = [1] (탐색 시작 노드)
   • visited = {} (방문한 노드 없음)
   • result = [] (탐색 결과 초기화)

1단계: 1 탐색

• queue = [1] → queue.popleft()로 1 꺼냄.
• 방문 처리: visited = {1}
• 결과에 추가: result = [1]
• 인접 노드 2, 3 추가:
  • queue = [2, 3]

2단계: 2 탐색

• queue = [2, 3] → queue.popleft()로 2 꺼냄.
• 방문 처리: visited = {1, 2}
• 결과에 추가: result = [1, 2]
• 인접 노드 4 추가:
  • queue = [3, 4]

3단계: 3 탐색

• queue = [3, 4] → queue.popleft()로 3 꺼냄.
• 방문 처리: visited = {1, 2, 3}
• 결과에 추가: result = [1, 2, 3]
• 인접 노드 5 추가:
  • queue = [4, 5]

4단계: 4 탐색

• queue = [4, 5] → queue.popleft()로 4 꺼냄.
• 방문 처리: visited = {1, 2, 3, 4}
• 결과에 추가: result = [1, 2, 3, 4]
• 인접 노드 없음:
  • queue = [5]

5단계: 5 탐색

• queue = [5] → queue.popleft()로 5 꺼냄.
• 방문 처리: visited = {1, 2, 3, 4, 5}
• 결과에 추가: result = [1, 2, 3, 4, 5]
• 인접 노드 없음:
  • queue = []

6단계: 탐색 종료

• queue = [] (큐가 비었으므로 탐색 종료).

---

### 문제 39 다익스트라 알고리즘

import heapq

def dijkstra(graph, start):
    # 최단 거리 저장용 리스트 (초기값: 무한대)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  # 시작 노드의 최단 거리는 0

	# 탐색할 노드를 저장하는 우선순위 큐 초기화
    priority_queue = [(0, start)]  # (거리, 노드)

    while priority_queue:
        # 가장 짧은 거리의 노드 꺼냄
        current_distance, current_node = heapq.heappop(priority_queue)

        # 이미 처리된 노드는 무시
        if current_distance > distances[current_node]:
            continue

        # 인접 노드 확인
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            # 최단 거리가 갱신되면 큐에 추가
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

### 문제 40 벨만포드 알고리즘

def bellman_ford(graph, start, num_nodes):
    # 최단 거리 저장용 리스트 (초기값: 무한대)
    distances = [float('inf')] * num_nodes
    distances[start] = 0  # 시작 노드의 최단 거리는 0

    # 모든 간선을 (|V| - 1)번 반복
    for _ in range(num_nodes - 1):
        for u, v, weight in graph:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    # 음수 사이클 확인 (|V|번째 탐색)
    for u, v, weight in graph:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            return "Negative weight cycle detected"

    return distances