DFS/BFS 알고리즘

미리 알고있어야 하는 개념

1. 재귀함수 (Recursive Function) : 자기자신을 다시 호출하는 함수

def recursive_function() :
		print('재귀 함수를 호출합니다.')
		recursive_function()

recursive_function()

위에 코드를 실행하면 ‘재귀 함수를 호출합니다.’ 라는 문자열을 무한히 출력한다.

2. 스택 (Stack) : 선입후출 구조 또는 후입선출 구조
3. 큐 (Queue) : 선입 선출 구조
4. 2차원 리스트 입력 받는 법

n, m = map(int,input().split())

#1
mylist = [0 for _ in range(n)]
for i in range(n)
        mylist[i] = list(map(int, input().split()))

#2
mylist = []
for i in range(n):
        mylist.append(list(map(int, input().split())))

#3
mylist = [list(map(int, input().split())) for _ in range(n)]

#결과
print(mylist)
#[ [0,1,0,0], [0,0,0,0], [0,0,1,0] ]

DFS ( Depth-First Search )

DFS란? 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 말한다.

• 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  https://namu.wiki/w/인접행렬
• 인접 리스트 : 리스트로 그래프의 연결관계를 표현하는 방식
• 동작 과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

# DFS 메서드 정의
def dfs(graph, v, visited) :
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end ='')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v] :
        if not visited[i] :
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

출력 : 12768345

BFS (Breadth First Search)

BFS 란? 너비 우선 탐색 , 가까운 노드부터 탐색하는 알고리즘

• 동작 방식
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
  3. 2번의 과정을 더 이상 수행 할 수 없을때 까지 반복한다.

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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출 
bfs(graph, 1, visited)

출력 : 12387456

코딩 테스트에서 보통 DFS 보다는 BFS 구현이 조금 더 빠르게 동작한다.

문제

• 조건

1. 두 정점 사이에 여러개의 간선이 있을 수 있다.
2. 입력으로 주어지는 간선은 양방향이다.

풀이

인접행렬

https://namu.wiki/w/인접행렬

• 단위 행렬
  어떤 그래프의 인접행렬이 단위행렬이라면 각 정점에 대해 자기 자신과 연결되는 간선만 존재하는 그래프이다. 이때 몇 step이든 간에 자기 자신으로만 이동할 수 있고 그 경우의 수는 자기 자신으로만 계속해서 이동하는 경우 1가지뿐이므로 인접행렬의 몇 제곱이든 간에 주대각선의 성분만 1이고 나머지 성분은 모두 0인 단위행렬이 된다.
• 영행렬
  인접행렬이 영행렬이라는 것은 그래프의 간선이 하나도 없다는 뜻이다. 즉, 어떤 정점에서 자기 자신이든 다른 정점으로든 이동이 전혀 불가능하다는 것을 의미한다. 따라서 몇 step이든 간에 이동 자체가 불가능하므로 인접행렬의 몇 제곱이든 간에 똑같이 영행렬이다.

코드

#백준 1260번 : DFS 와 BFS

from collections import deque

# DFS 메서드 정의
def dfs(v) : 
    visit_dfs[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드 재귀적 방문 
    for i in range(1, n+1):
        if not visit_dfs[i] and graph[v][i] == 1:
            dfs(i)

# BFS 메서드 정의
def bfs(v) :
    queue = deque([v])
    visit_bfs[v] = True  

    # 큐가 빌 때까지 
    while queue :           
        # 큐에서 하나의 원소 뽑아 출력 
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 원소 큐에 삽입 
        for i in range(1, n+1):
            if not visit_bfs[i] and graph[v][i] == 1:
                queue.append(i)
                visit_bfs[i] = True

# 정점 개수, 간선 개수, 탐색 시작점 
n, m, v = map(int,input().split())

# 방문 체크
visit_dfs = [False] * (n+1)
visit_bfs = [False] * (n+1) 
graph = [[0]*(n+1) for i in range(n+1)]

# 노드 연결 -> 인접 리스트 
for _ in range(m) : 
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

dfs(v)
print()
bfs(v)