[알고리즘] - DFS 와 BFS

LIST

1. 재귀함수
2. DFS
3. BFS

 

intro

---

 

 

1. 재귀함수 - https://www.acmicpc.net/workbook/view/2052

2.DFS - https://www.acmicpc.net/workbook/view/9901 , https://school.programmers.co.kr/learn/courses/30/parts/12421

 

 

 

 

 

 

그래프 탐색 (Graph Algorithms):
   - 깊이 우선 탐색 (Depth-First Search, DFS): 그래프의 깊은 부분을 우선 탐색하는 방법.
   - 너비 우선 탐색 (Breadth-First Search, BFS): 그래프의 인접한 노드를 우선 탐색하는 방법.

 

 

 

 

1. 재귀함수

---

재귀함수(Recursion Function)

 - 함수가 자기 자신을 호출하는 프로세스를 가지고 있으면 이 함수를 재귀함수라고 한다.

 

[문제]

3을 입력받으면 1부터 3까지를 재귀함수를 이용해 출력하는 프로그램 작성

https://11001.tistory.com/68

파이썬(python) 라이브러리 - itertools (순열, 조합, 누적합)

# 중복순열
#  매개변수 n,k에 자연수가 입력되면 1부터 n까지의 수 중에서 중복을 허락하여 k개를 뽑아 일열로 나열하는
#  방법의 수를 출력하는 프로그램을 작성하시오.
#  만약 n=3 , k=2 이면
def DFS(L, n, k, p):
    if L == k:
        for x in p:
            print(x, end="")
        print()
    else:
        for i in range(1, n+1):
            p.append(i)
            DFS(L+1, n, k, p)   # 9라인
            p.pop()


def solution(n, k):
    DFS(0, n, k, [])
    return "end"


print(solution(3, 2))

* 순열 , 조합 , 중복순열 , 중복조합

* 일정한 숫자 데이터셋에서 임의의 n개를 뽑는다면........ 

* 순서와 중복 여부에 따라...........순열 , 조합 , 중복순열 , 중복조합

*순열은 순서를 따진다 (조합은 순서 상관 없으므로 동일 숫자로 이루어져 있으면 제외한다.)

*동일 숫자가 2번이상 뽑힌다면 중복이다.

 

2. DFS

---

1.

#음료수 얼려먹기
# N x M 의 얼음틀이있음.  구멍: 0 , 칸막이 :1
# 구멍 뚫려있는 부분끼리 상하좌우 붙어 있는 경우 서로 연결되어 있는 것으로 간주함.
# 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 return

# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 0:
        # 해당 노드 방문 처리
        graph[x][y] = 1
        # 상하좌우의 위치들도 모두 재귀적으로 호출
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False


# n,m을 공백을 기준으로 구분하여 입력받음.
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
# ice = [[0,0,1,1,0],[0,0,0,1,1],[1,1,1,1,1],[0,0,0,0,0]]
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
print(graph)

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1

print(result)

3. BFS

---

https://www.freecodecamp.org/news/breadth-first-search-a-bfs-graph-traversal-guide-with-3-leetcodeexamples/

 

BFS(너비 우선 탐색 ; Breadth-First Search)

•  그래프나 트리와 같은 자료 구조에서 노드를 탐색하는 알고리즘 중 하나
•  시작 노드에서 시작하여 인접한 모든 노드를 먼저 탐색하고, 그다음 레벨의 노드들을 탐색
•  즉, 너비를 우선으로 탐색하며, 같은 레벨에 있는 노드들을 모두 방문한 후 다음 레벨의 노드들을 탐색하는 방법

 

 

특징

1. 큐(Queue) 자료구조를 사용: BFS는 방문한 노드들을 큐에 저장하면서 처리합니다. 먼저 방문한 노드를 큐에 넣고, 그 노드와 인접한 노드들을 순서대로 큐에 추가합니다.

2. 너비 우선 탐색: BFS는 인접한 노드들을 모두 방문한 후에 다음 레벨의 노드들을 방문합니다. 따라서 같은 레벨에 있는 노드들을 먼저 순회하게 됩니다.

3. 최단 경로 탐색: BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데에 주로 사용됩니다. 탐색 순서가 너비 우선이므로, 시작 노드로부터 가장 가까운 노드들을 먼저 방문하게 됩니다.

 

기본적인 동작 과정

1. 시작 노드를 큐에 넣고, 방문한 노드로 표시합니다.

2. 큐가 비어있지 않은 동안 반복합니다.
   - 큐에서 노드를 하나 꺼내옵니다(Dequeue).
   - 해당 노드와 인접한 미방문 노드들을 모두 큐에 넣고, 방문 처리합니다.

3. 큐가 비어질 때까지 반복하면 모든 노드를 방문하게 됩니다.

BFS는 주로 최단 경로, 그래프 연결 여부, 트리 순회 등에 활용됩니다. 시간 복잡도는 노드의 수를 V, 간선의 수를 E라고 할 때 O(V+E)입니다. 이는 모든 노드와 간선을 한 번씩만 방문하면 되기 때문입니다.

 

코드

1. 이진 트리에서 BFS

# BFS [Breadth-First Search] :레벨순으로 탐색한다.
# 루트노드(0레벨) , 1레벨 ,2레벨
# 활용 -> 출발에서 도착까지 최소로 도착할때 

# level 0: 1
# level 1: 2,3
# level 2: 4,5,6,7

# 순회 순서 : 1-2-3-4-5-6-7

from collections import deque


def BFS():
    dQ = deque()
    dQ.append(1)
    # print(type(dQ)) #<class 'collections.deque'>
    L = 0
    print(f"레벨: {L}")
    while (dQ):   # 큐가 비어있지 않은 동안 반복합니다.
        length = len(dQ)
        for v in range(length):  # 각 레벨 수준에서 처리해야할 노드의 개수만큼 반복
            v = dQ.popleft()
            print(v, end=" ")
            for nv in [v*2, v*2+1]: # 동일 레벨 수준에서 출력될 노드 값 패턴지정및 반복문으로 조회
                if nv > 7:
                    continue
                dQ.append(nv)
            L += 1


BFS()

 

2. 레벨당 가지가 3개씩 증가할 경우

from collections import deque

def BFS():
    dQ = deque()
    dQ.append(1)
    level = 0
    branch_factor = 3
    
    while dQ:
        num_nodes_in_level = len(dQ)
        print(f"Level {level}: ", end="")
        
        for _ in range(num_nodes_in_level):
            node = dQ.popleft()
            print(node, end=" ")
            
            for i in range(1, branch_factor + 1):
                child_node = node + i + level * branch_factor
                dQ.append(child_node)
        
        print()
        level += 1

BFS()

 

3. 

from collections import deque

def solution(s, e):
    answer=0
    ch=[0]*10001
    dq=deque()
    dq.append(s)
    ch[s]=1
    L=0
    while dq:
        length=len(dq)
        for _ in range(length):
            x=dq.popleft()
            for nx in [x-1,x+1,x+5]:
                if nx ==e:
                    return L+1
                if nx>0 and nx <=10000 and ch[nx] ==0:
                    ch[nx]=1
                    dq.append(nx)
        L+=1

3.1.   3번과 코드 비교해보기 ( 속도가 느린 이유)

from collections import deque

def solution(s, e):
    dQ = deque()
    dQ.append(s)
    level = 0
    branch_factor = 3
    
    while dQ:
        num_nodes_in_level = len(dQ)
        
        for _ in range(num_nodes_in_level):
            node = dQ.popleft()
            
            if node == e:
                return level
            
            for i in range(1, branch_factor + 1):
                child_node = 0
                if i == 1:
                    child_node = node - 1
                elif i == 2:
                    child_node = node + 1
                elif i == 3:
                    child_node = node + 5
                
                dQ.append(child_node)
        
        level += 1