[알고리즘 with Python] - DFS, BFS

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈

 

1. 그래프 표현 방법

- 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프 관계 표현

- 인접 리스트(Adjacency List): 리스트로 그래프 관계 표현

 

2. DFS 구현

# DFS 함수 정의하기
def dfs(graph, v, visited):
    # 1. 현재 노드 방문 처리하기.
    visited[v] = True
    print("visited node:",v)

    # 2. 현재 노드와 연결된 다른 노드 재귀적으로 방문하기.
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
    
    # 확인용 코드 (이 밑의 코드는 없어도 무방)
    # 3. 모두 방문했다면 해당 dfs를 종료하고 상위 dfs 함수로 넘어간다.
    print("해당 깊이의 노드 탐색 종료")   
    return

 

노드의 개수가 1000개 이상일 경우엔 깊이 한도를 늘려준다

import sys
sys.setrecursionlimit(10**6)

 

3. BFS 구현

from collections import deque

# BFS 함수 정의하기
# 1. 탐색 시작노드를 큐에 삽입하고 방문처리를 한다.
# 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노들르 모두 큐에 삽입하고 방문처리를 한다.
# 3. 반복

def bfs(graph, start, visited):
    queue = deque([start])
    
    visited[start] = True   # 현재노드 방문 처리
    # Queue가 빌 때까지 반복
    while queue:
        # Queue에서 가장 왼쪽의 원소 뽑아 출력하기
        v = queue.popleft()
        print(v, end =' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

 

4. graph 입력 TIP

# 백준 1260번을 참고했습니다.

# 노드의 개수를 n, 양방향 간선의 개수를 m, 탐색 시작 노드를 n이라고 할 때:
n, m, v = map(int,sys.stdin.readline().split())

# 2중 리스트 만들기 -> list complihension 이용하기!
graph = [[] for _ in range(n+1)]     
visited = [False] * (n+1)

# 주어진 입력으로 간선 만들기
for i in range(m):
    node1, node2 = map(int,sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)
for i in graph:
    i.sort()