문제 출처 : https://www.acmicpc.net/problem/1260
탐색 알고리즘인 DFS와 BFS를 정말 원론적으로 구현해내는 문제
강의를 듣고 책을 찾아보면서 DFS와 BFS를 이해하고 있다 생각했는데 이틀동안 반례를 찾지 못해서 허덕였다... 하지만 결국 내 잘못이지 역시 항상 자기자신부터 돌아봐야지 암암
암튼! 잠시 DFS와 BFS를 다시 한 번 재정립하는 과정을 가지면서 온전히 내 것으로 만들자
혹시 이 글을 보시는 분이 있을지는 모르겠지만 저 스스로 다시 한 번 되새기며 공부하는 과정이니 오류가 있다면 귀여워하는 마음으로 잡아주시면 감사한 마음으로 수정하도록 하겠습니다
자 일단 DFS와 BFS 둘 다 탐색 알고리즘의 종류이다 ( 이 밖에도 수많은 탐색 알고리즘이 있겠지만 아직 안 배웠으니 그냥 패스 )
그 중 그래프를 자료구조로 가지는 데이터 셋을 탐색할 때 사용한다. 여기서 그래프란 무엇인가? 단순히 말하자면 노드( 라고도 하지만 오토마타에서 익숙한 STATE 라고 이해하니까 편하더라 ) 와 그 노드들을 잇는 간선(EDGE)으로 이루어진 자료구조이다. 부가적인 설명으로는 트리와 다르게 루트노드X,부모자식X,네트워크 모델에 주로 사용됨 등이 있다.
다시 돌아와서!
DFS란?
DFS는 deep-first-search, 깊이 우선 탐색으로 어떤 그래프 안에서 시작점(start node)을 주어졌을때, 시작점을 기반으로 다른 node들을 탐색할때 깊이를 우선적으로 생각해서 탐색한다는 것이다. 한 node(1)에서 다른 node(2)로 넘어가면, 이 node(2)에서 다시 다른 node(3)로 넘어가는 것이다. 즉 내가 파고 있는 node를 계속 판다. 한 놈만 판다! 라는 느낌
BFS란?
BFS는 Breath-first-seartch, 너비 우선 탐색으로 어떤 그래프 안에서 시작점(start node)을 주어졌을 때, 시작점을 기반으로 다른 node들을 탐색할때 너비를 우선적으로 생각해서 탐색한다는 것이다. 한 node(1)에서 다른 node로 바로 넘어가는 게 아니라 node(1)에 간선으로 연결되어 있는 모든 node들(2,3,4 )을 탐색하는 것이다. 그리고 순차적으로 node(2)에 연결되어 있는 모든 node들을 탐색하고, node(3)에 연결되어 있는 모든 node들을 탐색하는 것이다.
각 특징으로는
DFS의 특징
*재귀를 사용하는 순환 알고리즘의 성격을 띤다
*내 코드에서는 STACK을 사용하진 않았지만 명시적으로 나타내기 위해 STACK을 쓴다.BFS의 특징
*재귀를 사용하는 것 같아 보이지만 QUEUE를 참조하여 차례대로 저장후 꺼낸다.(FIFO)공통적으로 그래프 탐색의 경우 꼬리물고 연결되어 한 NODE를 참조하고 다시 그 NODE를 마주치는 경우가 많기 때문에 꼭 노드의 방문여부를 검사해야 한다. ( VISTIED )
이 둘을 언제 써야 적시적소에 사용하는 것일까?
DFS의 경우 백트래킹이랑 비슷한 느낌? 한 길로 끝까지 가보다가 더이상 갈수 없으면 다시 다음 갈림길로 가는 방식. ( 이렇게 생각해보면 백트래킹은 가지치기를 통해 바로바로 길을 삭제시키니까 DFS보다 효율적이겠네, DFS는 모든 길을 탐색,방문하니까 )
BFS의 경우 두 노드 간의 연결성을 탐색할 때, 모든 길을 탐색하는 게 아니라 특정 길을 찾고 싶을 때 또는 최단경로를 구하고자 할때 주로 쓰는 방식
코드
from collections import defaultdict
from collections import deque
import sys
N,M,V = list(map(int,sys.stdin.readline().rstrip("\n").split()))
Dvisited = [0 for _ in range(1001)]
Bvisited = [0 for _ in range(1001)]
link = defaultdict(list)
for m in range(M) :
s1, s2 = list(map(int,sys.stdin.readline().rstrip("\n").split()))
if s2 in link[s1] :
continue
link[s1].append(s2)
link[s2].append(s1)
for n in link.keys() :
link[n].sort()
def dfs(state) :
Dvisited[state]+=1
print(state,end=" ")
for next_s in link[state] :
if not Dvisited[next_s] :
dfs(next_s)
dfs(V)
print('')
dq=deque([V])
Bvisited[V]+=1
def bfs(state) :
while dq :
s=dq.popleft()
print(s,end=" ")
for next_s in link[s] :
if not Bvisited[next_s] :
dq.append(next_s)
Bvisited[next_s]+=1
bfs(V)최근 파이썬 알고리즘 인터뷰에서 defaultdict를 배우고 이걸 사용해서 만들수있겠다. 라는 생각으로 이를 활용하여 코드를 작성했다. ( dict는 참조시간이 O(1)이니까! ) 그리고 추가로 이렇게 하면 2차원 배열을 쓰는 것보다 메모리 사용량이 더 적을거라고 판단하여 코드를 작성했다.
하지만 메모리 사용량이 내가 더 많았다 왜지? ( yoonsung51님을 보고 배우자 )
*참고로 grapgh 를 2차원 배열로 만들어 간선(i,j)가 있으면 graph[i][j]=1 이런 방식도 있었고, graph[i].append(j) 이런 방식도 있었다.결과적으로 여러 번의 실패가 있었다.
1. 공부하면서 다시 알게됐지만 BFS는 재귀가 아니다! 그런데 재귀로 짜버리니 오류가 나지
2. 중복되는 간선이 있을거라 생각못했다. 문제를 제대로 안 읽은 내 잘못이긴 하지... 문제를 보고 문제를 구조화시켜 정확하게 한 번에 풀자.
3. 분명 오류나는 지점이 어디있을텐데 제대로 분석해서 문제를 가시화하고 해결하는 습관을 들이자
이 정도로 실패하고 했으면 머릿속에서 DFS와 BFS는 바로바로 떠오르겠지?
