TIL_4 | algorithm - BFS/DFS

code_sign·2021년 1월 2일

algorithm

목록 보기

2/4

코딩 테스트를 준비하면서 PS(Problem Solving)이 문제를 풀었다면 그 다음 단계는 BFS/DFS 알고리즘이다. 이 알고리즘을 알기 위해선 재귀함수를 먼저 아는것이 중요한데, 재귀함수란 '자신을 호출하는 함수'라고 이해하면 된다.

재귀함수의 대표적인 예: 팩토리얼(factorial)

학창시절에 흔히 써먹었던 팩토리얼(factorial)을 생각하면 된다.

반복적으로 구현한 n!

def factorial_iterative(n):
	result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n + 1):
    	result += 1
    return result

위의 코드는 재귀함수를 사용하지 않고 반복만으로 구현한 코드다. 결과값 result에 계속 값을 더해 return한다.

재귀적으로 구현한 n!

def factorial_recursive(n):
	if n <= 1:
    	return 1
    # n! = n * (n - 1)!를 그대로 코드로 작성하기
    return n * factorial_recursive(n - 1)

이것이 바로 재귀함수를 이용한 팩토리얼이다. 파라미터 값으로 n - 1을 받아서 하나씩 줄여나가다 보면 2번째 줄인 if문에서 return해주는 값이 나온다.

재귀함수의 가장 중요한 점은 escape문을 만들어 함수가 끝이 날 수 있또록 하는 것이다. (return이든 break이든..)

재귀함수를 약....간! 이라도 이해를 했다면 BFS/DFS를 공부하는데 훨씬 순조로울 것이다!

BFS/DFS

BFS(Breadth First Search)

약어 그대로 '넓이 우선 탐색' 알고리즘이다. 같은 라인에 존재하는 값들에 대한 우선 탐색인데 글로만 이해하기에는 어려운 개념이다.

위의 그림과 같이 최상단 노드 혹은 시작 노드를 시작하여 인접한 간선의 노드로 향하고, 그것들을 넓게 탐색하는 알고리즘이다.
(참조: BFS, Wikimedia Commons)

from collections import deque

def bfs(graph, start, visited):
    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

# e는 edge
visited = [False] * (e + 1)

파라미터로 graph, start, visited를 받게 되는데 graph는 list타입으로 0번 index 자리에는 항상 빈 리스트([])가 들어간다. 그래서 graph의 길이는 e + 1의 값이 된다.

visited의 타입도 list이며 코드에서 볼 수 있듯이 False(혹은 0)으로 세팅하고 방문했을때 True(혹은 1)을 대입해줘서 같은 곳을 들리지 않도록 한다.

이유는 그렇게 함으로써 노드의 번호에 -1 같은 코드를 안쓰는 편리함 때문이다.

BFS 알고리즘은 queue 자료형을 사용한다. queue 자료형은 LIFO(Last In Last Out) 자료구조로 값에대해 선입선출이 이루어진다.

collections의 deque자료형은 양방향으로 IN/OUT이 가능하기에 편리하다. popleft()의 수행에도 O(N)만큼의 시간만 소요되기에 좋다.

DFS(Depth First Search)

(참조: BFS, Wikimedia Commons)

DFS는 '깊이 우선 탐색'이다. 같은 라인에 있는 노드들을 우선적으로 탐색하고 stack 자료형에 기록한다. stack 자료형은 LIFO(Last In First Out) 자료구조로 후입선출이 이루어진다. 나가는 방향이 한방향이라고 생각하면 좋다.

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

나머지는 BFS에서 설명한것과 같지만 BFS와 가장 다른 차이점은 재귀함수로 작동한다는 점이다.

마지막줄의 코드를 보면 다시 bfs함수를 호출하는 것을 볼 수 있는데, 그럼으로써 깊이 우선 탐색이 가능하다!

이해가 잘 가지 않는다면 복붙하여 debug로 실행해보는 것을 추천한다!

💡주의! index대로 정렬된 상태의 리스트를 input 하자💡

[
[1, 6],
[1, 3],
[6, 4],
[2, 5],
[4, 1]
]

만약 위와 같은 input이 들어온다면 정렬되지 않았기 때문에 잘못된 값을 return 할 수 있다. 그래서 우리는 다시 한번 정렬된 상태를 만들기 위해 정리를 해 줄 필요가 있다.

graph = []
for i in range(1, n + 1):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

이와 같이 코드를 짜면 각 index별로 정렬이 되어 잘 작동할 것이다!

Today, learned?

배운점

BFS/DFS, 재귀함수 지옥.... 살려줘....😂
정렬을 해주고 input을 해줘야한다!~~(내 소중한 삽질 한시간..)~~
이분그래프?? BOJ 1707번 문제.... (색이 다르고, 뭐가 저렇구...)

느낀점

이분탐색 할때 쉽다고 좋아했는데.. 그리디만 어렵다고 생각했는데, BFS/DFS도 어렵구나..
내 머리는 수학머리가 아닌가 수학의 정석을 다시 풀어봐야 하나 고민이 된다. (미대생은 웁니닼ㅋㅋㅋㅋ)
그래도 github 잔디를 꾸준히 심고 있어서 마음에 안정이 온다...! (feat. 1일1커밋)
아직도 velog 글을 개념정리 위주로 올려야 하는지.. 아니면 일기 형식으로 올려야 하는지.. TIL에 맞게 하루에 하나만 올려야 할지.. 주제별로 여러개 올려도 될지 고민이 되고 너무 어렵다...!