드디어 그놈들이 나왔다. 1주일동안 정글 교육생들 사이에서 가장 뜨거운 주제 2개이다.
BFS/DFS 알고리즘은 그래도 처음에는 어려웠는데
백준 풀라고 준 문제에서 반복학습을 몇번씩 해 봤기 때문에 지금은 할만한 것 같다.
BFS
정말 설명이 잘 되어 있는 그림이다.
단순하게 레벨이 작은 노드들부터 같은 레벨의 왼쪽부터 오른쪽으로, 한 레벨의 노드를 모두 스캔 했으면
다음 레벨로 넘어가는 것이다.
위 그림에서 BFS 알고리즘으로 탐색을 하게 된다면
A -> B , C , D -> E , F , G , H가 될 것이다.
이제 코드를 봐 보자.
def bfs(V):
q = deque([V])
visited2[V] = True
while q:
V = q.popleft()
print(V, end=" ")
for i in range(1, N + 1):
if not visited2[i] and graph[V][i]:
q.append(i)
visited2[i] = True
백준 1260번 dfs/bfs 문제에서 bfs 실행 구문이다.
생각보다 좀 긴데 풀이를 하자면
- deque로 큐를 하나 만들어준다.
- 방문한 인덱스는 다시 안가도록 visit = True로 막는다.
- while q 구문 -> 시작점을 pop 해서 v에 저장한다.
- v에 연결된 인덱스들을 모두 찾아 append 한다.
- append 할때 추가하는 인덱스들의 visited도 True로 바꾼다.
이렇게 하면 A에 연결된 B , C , D가 append 되고
B , C , D가 차례로 E , F , G , H를 append 하고...
이런 방식으로 BFS 알고리즘이 완성된다.
DFS
'일반적으로 'DFS가 BFS보다 코드짜기 훨씬 수월하다.
그냥 반복 제귀문 돌려버리면 끝나기 때문이다.
def dfs(V):
visited1[V] = True
print(V, end=" ")
for i in range(1, N + 1):
if not visited1[i] and graph[V][i]:
dfs(i)
무려 코드가 5줄에 끝이 나버린다.
- 방문한 노드의 visited를 True로 만든다.
- print 한 후, 자식노드들을 전부 dfs함수 돌려버린다.
- 제귀 돌려놓으면 자동사냥 하는것마냥 알아서 다 찾아본다.
이 얼마나 편한 방법인지 모르겠다.
근데 dfs는 함수를 반복적으로 불러오기 때문에 메모리랑 시간을 무지막지하게 잡아먹는다.
근데 계산량이 적고 최적화를 잘 시키면 백준문제 풀때 막 써도 통과가 엄청 잘된다.
앞으로 요긴하게 쓸 것 같다.
닭이 되고싶은 병아리